Right Triangles

Medium

Asked by:

21 views

Topics:

Arrays

You are given a 2D boolean matrix grid.

A collection of 3 elements of grid is a right triangle if one of its elements is in the same row with another element and in the same column with the third element. The 3 elements may not be next to each other.

Return an integer that is the number of right triangles that can be made with 3 elements of grid such that all of them have a value of 1.

Example 1:

0	1	0
0	1	1
0	1	0

0	1	0
0	1	1
0	1	0

0	1	0
0	1	1
0	1	0

Input: grid = [[0,1,0],[0,1,1],[0,1,0]]

Output: 2

Explanation:

There are two right triangles with elements of the value 1. Notice that the blue ones do not form a right triangle because the 3 elements are in the same column.

Example 2:

1	0	0
0	1	1
1	0	0

Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

Output: 0

Explanation:

There are no right triangles with elements of the value 1. Notice that the blue ones do not form a right triangle.

Example 3:

1	0	1
1	0	0
1	0	0

1	0	1
1	0	0
1	0	0

Input: grid = [[1,0,1],[1,0,0],[1,0,0]]

Output: 2

Explanation:

There are two right triangles with elements of the value 1.

Constraints:

1 <= grid.length <= 1000
1 <= grid[i].length <= 1000
0 <= grid[i][j] <= 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the data types and ranges of the coordinates representing the points? Can they be floating-point numbers, and can they be negative?
Are there any constraints on the number of points in the input? What is the maximum number of points I should expect?
How should I handle duplicate points? Are they considered distinct points when forming right triangles?
If no right triangles can be formed from the given points, what should the function return? Should I return null, an empty list, or throw an exception?
Does the order of points in the returned triangle matter? For instance, is (A, B, C) considered the same as (B, A, C)?

Brute Force Solution

Approach

The brute force strategy for finding right triangles from a collection of points involves checking every possible combination of three points. We then test if those three points form a right triangle. If they do, we count it, and we continue until we've checked all possible combinations.

Here's how the algorithm would work step-by-step:

Take the first three points from the collection.
Determine the distance between each pair of these three points.
Use the Pythagorean theorem (a squared plus b squared equals c squared) to check if the squared distances satisfy the condition for a right triangle.
If the condition is satisfied, increment the counter.
Now, pick a different set of three points. Repeat this process for every single possible combination of three points from the collection.
Once you have examined every possible combination of three points, the counter will hold the total number of right triangles found.

Code Implementation

def find_right_triangles_brute_force(points):
    number_of_points = len(points)
    right_triangle_count = 0

    # Iterate through all possible combinations of three points
    for first_point_index in range(number_of_points):
        for second_point_index in range(first_point_index + 1, number_of_points):
            for third_point_index in range(second_point_index + 1, number_of_points):
                first_point = points[first_point_index]
                second_point = points[second_point_index]
                third_point = points[third_point_index]

                # Calculate the squared distances between each pair of points
                distance_squared_12 = (first_point[0] - second_point[0])**2 + (first_point[1] - second_point[1])**2
                distance_squared_13 = (first_point[0] - third_point[0])**2 + (first_point[1] - third_point[1])**2
                distance_squared_23 = (second_point[0] - third_point[0])**2 + (second_point[1] - third_point[1])**2

                # Check if the Pythagorean theorem holds true for any combination
                # We must check all permutations to find the hypotenuse
                if (distance_squared_12 + distance_squared_13 == distance_squared_23) or \
                   (distance_squared_12 + distance_squared_23 == distance_squared_13) or \
                   (distance_squared_13 + distance_squared_23 == distance_squared_12):

                    # Increment counter if points form right triangle
                    right_triangle_count += 1

    return right_triangle_count

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force algorithm iterates through all possible combinations of three points from a collection of n points. This requires selecting 3 points out of n, which corresponds to a combination, and results in n choose 3, or n! / (3! * (n-3)!) possible combinations. Expanding this formula reveals that the dominant term is proportional to n * n * n, or n cubed. Checking if each combination of three points forms a right triangle involves a constant amount of work. Thus, the overall time complexity is O(n^3).

Space Complexity

O(1) – The provided solution calculates distances between points and checks the Pythagorean theorem. It uses a constant number of variables to store distances and the count of right triangles. Regardless of the number of points (N), the algorithm does not use any auxiliary data structures that scale with the input size. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key is to efficiently count how many points form right triangles by focusing on shared coordinates. We can organize the points by their x and y coordinates to quickly identify potential right triangles.

Here's how the algorithm would work step-by-step:

First, count how many points share the same x-coordinate and how many share the same y-coordinate.
For each point, look at the number of other points that have the same x-coordinate and the number of other points that have the same y-coordinate.
Multiply these two numbers together for each point. This gives you the number of right triangles that can be formed with this point as the right angle vertex.
Finally, add up all these products for all the points to get the total number of right triangles.

Code Implementation

def right_triangles(points):
    x_coordinates = {}
    y_coordinates = {}

    for x, y in points:
        if x not in x_coordinates:
            x_coordinates[x] = 0
        x_coordinates[x] += 1

        if y not in y_coordinates:
            y_coordinates[y] = 0
        y_coordinates[y] += 1

    number_of_right_triangles = 0

    # Iterate through each point to calculate potential right triangles.
    for x, y in points:

        # Exclude the point itself from the count.
        points_with_same_x = x_coordinates[x] - 1
        points_with_same_y = y_coordinates[y] - 1

        # Count triangles with this point as the right angle.
        number_of_right_triangles += points_with_same_x * points_with_same_y

    return number_of_right_triangles

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the points once to count x and y coordinates frequencies, which takes O(n) time. Then, it iterates through the points again to calculate right triangles using the precomputed frequencies, which also takes O(n) time. Adding these two iterations results in O(n) + O(n), which simplifies to O(n). The number of points 'n' drives the cost, and the operations are proportional to 'n'.

Space Complexity

O(N) – The solution uses two dictionaries (or hash maps) to store the counts of points sharing the same x-coordinate and y-coordinate, respectively. In the worst-case scenario, all N points have distinct x and y coordinates, leading to both dictionaries storing N key-value pairs. Therefore, the auxiliary space used is proportional to the number of points N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input lists for x, y coordinates	Return 0, as no triangles can be formed with no points.
Null input lists for x, y coordinates	Throw an IllegalArgumentException or return an error code indicating invalid input.
Input lists x and y have different lengths	Throw an IllegalArgumentException as the coordinates need to correspond one-to-one.
All points are collinear (lie on a straight line)	Return 0, as no right-angled triangle can be formed from collinear points.
Integer overflow when calculating distances (squared)	Use long data types for squared distances to prevent potential integer overflows.
Duplicate points in the input	The distance calculation and counting logic should handle duplicate points correctly by considering all possible combinations.
Large number of points causing memory issues if all combinations are pre-calculated	Employ an approach that avoids pre-calculating all combinations, instead calculating distances on demand to conserve memory.
X or Y coordinate values are very large leading to potential overflow errors when computing distances	Use long datatype to store X and Y coordinates, and use long arithmetic when calculating distances to avoid integer overflow.

Empty input lists for x, y coordinates

How to Handle:

Return 0, as no triangles can be formed with no points.

Null input lists for x, y coordinates

How to Handle:

Throw an IllegalArgumentException or return an error code indicating invalid input.

Input lists x and y have different lengths

How to Handle:

Throw an IllegalArgumentException as the coordinates need to correspond one-to-one.

All points are collinear (lie on a straight line)

How to Handle:

Return 0, as no right-angled triangle can be formed from collinear points.

Integer overflow when calculating distances (squared)

How to Handle:

Use long data types for squared distances to prevent potential integer overflows.

Duplicate points in the input

How to Handle:

The distance calculation and counting logic should handle duplicate points correctly by considering all possible combinations.

Large number of points causing memory issues if all combinations are pre-calculated

How to Handle:

Employ an approach that avoids pre-calculating all combinations, instead calculating distances on demand to conserve memory.

X or Y coordinate values are very large leading to potential overflow errors when computing distances

How to Handle:

Use long datatype to store X and Y coordinates, and use long arithmetic when calculating distances to avoid integer overflow.