Jobs

Interviews

Discussions

Find Maximum Area of a Triangle

Medium

Asked by:

34 views

Topics:

Arrays

You are given a 2D array coords of size n x 2, representing the coordinates of n points in an infinite Cartesian plane.

Find twice the maximum area of a triangle with its corners at any three elements from coords, such that at least one side of this triangle is parallel to the x-axis or y-axis. Formally, if the maximum area of such a triangle is A, return 2 * A.

If no such triangle exists, return -1.

Note that a triangle cannot have zero area.

Example 1:

Input: coords = [[1,1],[1,2],[3,2],[3,3]]

Output: 2

Explanation:

The triangle shown in the image has a base 1 and height 2. Hence its area is 1/2 * base * height = 1.

Example 2:

Input: coords = [[1,1],[2,2],[3,3]]

Output: -1

Explanation:

The only possible triangle has corners (1, 1), (2, 2), and (3, 3). None of its sides are parallel to the x-axis or the y-axis.

Constraints:

1 <= n == coords.length <= 10⁵
1 <= coords[i][0], coords[i][1] <= 10⁶
All coords[i] are unique.

Try coding it in LeetCode

Find Maximum Area of a Triangle

Medium

Asked by:

34 views

Topics:

Arrays

You are given a 2D array coords of size n x 2, representing the coordinates of n points in an infinite Cartesian plane.

If no such triangle exists, return -1.

Note that a triangle cannot have zero area.

Example 1:

Input: coords = [[1,1],[1,2],[3,2],[3,3]]

Output: 2

Explanation:

The triangle shown in the image has a base 1 and height 2. Hence its area is 1/2 * base * height = 1.

Example 2:

Input: coords = [[1,1],[2,2],[3,3]]

Output: -1

Explanation:

The only possible triangle has corners (1, 1), (2, 2), and (3, 3). None of its sides are parallel to the x-axis or the y-axis.

Constraints:

1 <= n == coords.length <= 10⁵
1 <= coords[i][0], coords[i][1] <= 10⁶
All coords[i] are unique.

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 is the maximum number of points that can be in the input list, and what is the range of possible x and y coordinate values?
Can the input list of points be empty or contain fewer than three points? If so, what should I return?
Are the x and y coordinates guaranteed to be integers, or could they be floating-point numbers? If floating-point, what level of precision is required for the area calculation?
If multiple sets of three points yield the same maximum area, is any one of those sets acceptable, or is there a specific criterion for choosing between them?
Are duplicate points allowed in the input? If so, should I consider them as distinct points when forming triangles?

Brute Force Solution

Approach

The brute force approach to finding the maximum triangle area is like trying every single combination of three points to see which one makes the biggest triangle. We calculate the area for each possible triangle and keep track of the largest area we've seen so far.

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

Consider each possible group of three points from the given list of points.
For each group of three points, calculate the area of the triangle they form.
Compare the calculated area with the largest area found so far.
If the current triangle's area is larger than the largest area found so far, update the largest area.
Repeat this process for all possible groups of three points.
After checking all possible triangles, the largest area found is the maximum area of a triangle formed by any three points from the list.

Code Implementation

def find_maximum_area_of_a_triangle(points):
    number_of_points = len(points)
    maximum_area = 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):

                # Get the three points for the current triangle
                point_one = points[first_point_index]
                point_two = points[second_point_index]
                point_three = points[third_point_index]

                # Calculate the area of the triangle using the determinant method.
                area = 0.5 * abs(
                    point_one[0] * (point_two[1] - point_three[1]) +
                    point_two[0] * (point_three[1] - point_one[1]) +
                    point_three[0] * (point_one[1] - point_two[1])
                )

                # Keep track of the largest area found
                if area > maximum_area:
                    maximum_area = area

    return maximum_area

Big(O) Analysis

Time Complexity

O(n^3) – The provided brute force solution iterates through all possible combinations of three points from the input list of points to find the triangle with the maximum area. Given n points, we need to consider all triplets. The number of such triplets is proportional to n choose 3, which is n! / (3! * (n-3)!). This expands to approximately n * (n-1) * (n-2) / 6. Ignoring the constant factors and lower order terms, the dominant term is n^3, therefore, the time complexity is O(n^3).

Space Complexity

O(1) – The brute force approach only uses a constant amount of extra space. It calculates the area of each triangle and keeps track of the maximum area found so far, requiring only a few variables to store intermediate calculations and the current maximum area, all of which are independent of the input size N (the number of points). No additional data structures that scale with the input are used; hence, the auxiliary space used is constant. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the largest triangle area formed by any three points from a given set of points. We avoid checking every possible triangle by cleverly using geometry to cut down the work we need to do. The key idea is to use the rotating calipers technique combined with the convex hull, a shape that encloses all the points.

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

First, find the 'convex hull' of all the points. Imagine stretching a rubber band around all the points; the shape it forms is the convex hull. Only points on the edge of this shape can be corners of the largest triangle.
Next, arrange the points on the convex hull in order, going around the shape in a circle.
Now, pick any one of the points on the convex hull to be a corner of our triangle, and keep it fixed for now.
Imagine two lines starting at the fixed point, each going to another point on the convex hull. Those other two points will be the other corners of our triangle. Imagine the two lines 'rotating' around the circle of points. This is similar to the rotating calipers algorithm for diameter.
As the lines rotate, we calculate the area of the triangle they form. We keep track of the maximum area we've seen so far.
The clever trick is that as one line rotates to the next point, we can predict which point the other line should go to next to maximize the triangle's area, based on the position of the first line's new point. This way, we don't have to check every single point combination.
After sweeping all lines around the fixed point, we now select the next point in the convex hull and fix it. Repeat the rotating lines process.
Once we've fixed every point of the convex hull, we can compare all the maximum areas calculated. The highest area is the area of the largest triangle that can be formed using three of the original points.

Code Implementation

def find_maximum_area_of_triangle(points):
    def cross_product(point1, point2, point3):
        return (point2[0] - point1[0]) * (point3[1] - point1[1]) - (point2[1] - point1[1]) * (point3[0] - point1[0])

    def calculate_area(point1, point2, point3):
        return 0.5 * abs(cross_product(point1, point2, point3))

    def convex_hull(points):
        points = sorted(points)
        if len(points) <= 1:
            return points
        
        upper_hull = []
        for point in points:
            while len(upper_hull) >= 2 and cross_product(upper_hull[-2], upper_hull[-1], point) <= 0:
                upper_hull.pop()
            upper_hull.append(point)
        
        lower_hull = []
        for point in reversed(points):
            while len(lower_hull) >= 2 and cross_product(lower_hull[-2], lower_hull[-1], point) <= 0:
                lower_hull.pop()
            lower_hull.append(point)

        return upper_hull[:-1] + lower_hull[:-1]

    convex_hull_points = convex_hull(points)
    number_of_hull_points = len(convex_hull_points)

    if number_of_hull_points < 3:
        return 0

    maximum_area = 0

    for i in range(number_of_hull_points):
        left_pointer = (i + 1) % number_of_hull_points
        right_pointer = (i + 2) % number_of_hull_points

        # Iterate through all possible combinations to maximize area.
        while True:
            area1 = calculate_area(convex_hull_points[i], convex_hull_points[left_pointer], convex_hull_points[right_pointer])
            next_right_pointer = (right_pointer + 1) % number_of_hull_points
            area2 = calculate_area(convex_hull_points[i], convex_hull_points[left_pointer], convex_hull_points[next_right_pointer])

            # Move right pointer if it leads to a bigger area.
            if area2 > area1:
                right_pointer = next_right_pointer
            else:
                maximum_area = max(maximum_area, area1)
                break
        
    return maximum_area

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first computes the convex hull, which takes O(n log n) time. Then, it iterates through each point on the convex hull (in the worst case, all n points are on the hull). For each point, a rotating calipers-like technique is used to find the optimal pair of other points, which takes O(n) time in total for a given fixed point. Since we repeat this process for each of the (at most) n points on the convex hull, the dominant cost is n * n. Therefore, the overall time complexity is O(n²), with the convex hull computation being dominated by this.

Space Complexity

O(N) – The dominant space usage comes from storing the convex hull, which, in the worst case, can contain all N input points. The rotating calipers algorithm itself uses a few index variables which contribute constant space. Therefore, the auxiliary space is primarily determined by the convex hull, resulting in O(N) space complexity where N is the number of input points.

Edge Cases

Case	How to Handle
Empty input list	Return 0, as no triangle can be formed.
Input list with fewer than 3 points	Return 0, as a triangle requires at least 3 points.
All points are collinear (lie on the same line)	Return 0, as a degenerate triangle has zero area.
Duplicate points in the input list	The area calculation formula will still work correctly; duplicates should not affect the maximum area found if they do not constitute one of the vertices of the maximum area triangle.
Integer overflow during area calculation with large coordinate values	Use a data type capable of holding larger values (e.g., long) or floating-point numbers (e.g., double) for the area calculation.
Floating-point precision issues when calculating area	Use a small tolerance value when comparing areas to account for potential floating-point inaccuracies.
Input list contains points with very large absolute coordinate values	Ensure that the chosen data types (e.g., int, long, double) can accommodate the range of coordinate values without overflow or loss of precision.
The three points that form the largest area triangle are close to being collinear	Floating-point imprecision might affect which triangle is identified, but should generally converge to correct area.

Empty input list

How to Handle:

Return 0, as no triangle can be formed.

Input list with fewer than 3 points

How to Handle:

Return 0, as a triangle requires at least 3 points.

All points are collinear (lie on the same line)

How to Handle:

Return 0, as a degenerate triangle has zero area.

Duplicate points in the input list

How to Handle:

The area calculation formula will still work correctly; duplicates should not affect the maximum area found if they do not constitute one of the vertices of the maximum area triangle.

Integer overflow during area calculation with large coordinate values

How to Handle:

Use a data type capable of holding larger values (e.g., long) or floating-point numbers (e.g., double) for the area calculation.

Floating-point precision issues when calculating area

How to Handle:

Use a small tolerance value when comparing areas to account for potential floating-point inaccuracies.

Input list contains points with very large absolute coordinate values

How to Handle:

Ensure that the chosen data types (e.g., int, long, double) can accommodate the range of coordinate values without overflow or loss of precision.

The three points that form the largest area triangle are close to being collinear

How to Handle:

Floating-point imprecision might affect which triangle is identified, but should generally converge to correct area.

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 is the maximum number of points that can be in the input list, and what is the range of possible x and y coordinate values?
Can the input list of points be empty or contain fewer than three points? If so, what should I return?
Are the x and y coordinates guaranteed to be integers, or could they be floating-point numbers? If floating-point, what level of precision is required for the area calculation?
If multiple sets of three points yield the same maximum area, is any one of those sets acceptable, or is there a specific criterion for choosing between them?
Are duplicate points allowed in the input? If so, should I consider them as distinct points when forming triangles?

Brute Force Solution

Approach

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

Consider each possible group of three points from the given list of points.
For each group of three points, calculate the area of the triangle they form.
Compare the calculated area with the largest area found so far.
If the current triangle's area is larger than the largest area found so far, update the largest area.
Repeat this process for all possible groups of three points.
After checking all possible triangles, the largest area found is the maximum area of a triangle formed by any three points from the list.

Code Implementation

def find_maximum_area_of_a_triangle(points):
    number_of_points = len(points)
    maximum_area = 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):

                # Get the three points for the current triangle
                point_one = points[first_point_index]
                point_two = points[second_point_index]
                point_three = points[third_point_index]

                # Calculate the area of the triangle using the determinant method.
                area = 0.5 * abs(
                    point_one[0] * (point_two[1] - point_three[1]) +
                    point_two[0] * (point_three[1] - point_one[1]) +
                    point_three[0] * (point_one[1] - point_two[1])
                )

                # Keep track of the largest area found
                if area > maximum_area:
                    maximum_area = area

    return maximum_area

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the 'convex hull' of all the points. Imagine stretching a rubber band around all the points; the shape it forms is the convex hull. Only points on the edge of this shape can be corners of the largest triangle.
Next, arrange the points on the convex hull in order, going around the shape in a circle.
Now, pick any one of the points on the convex hull to be a corner of our triangle, and keep it fixed for now.
Imagine two lines starting at the fixed point, each going to another point on the convex hull. Those other two points will be the other corners of our triangle. Imagine the two lines 'rotating' around the circle of points. This is similar to the rotating calipers algorithm for diameter.
As the lines rotate, we calculate the area of the triangle they form. We keep track of the maximum area we've seen so far.
The clever trick is that as one line rotates to the next point, we can predict which point the other line should go to next to maximize the triangle's area, based on the position of the first line's new point. This way, we don't have to check every single point combination.
After sweeping all lines around the fixed point, we now select the next point in the convex hull and fix it. Repeat the rotating lines process.
Once we've fixed every point of the convex hull, we can compare all the maximum areas calculated. The highest area is the area of the largest triangle that can be formed using three of the original points.

Code Implementation

def find_maximum_area_of_triangle(points):
    def cross_product(point1, point2, point3):
        return (point2[0] - point1[0]) * (point3[1] - point1[1]) - (point2[1] - point1[1]) * (point3[0] - point1[0])

    def calculate_area(point1, point2, point3):
        return 0.5 * abs(cross_product(point1, point2, point3))

    def convex_hull(points):
        points = sorted(points)
        if len(points) <= 1:
            return points
        
        upper_hull = []
        for point in points:
            while len(upper_hull) >= 2 and cross_product(upper_hull[-2], upper_hull[-1], point) <= 0:
                upper_hull.pop()
            upper_hull.append(point)
        
        lower_hull = []
        for point in reversed(points):
            while len(lower_hull) >= 2 and cross_product(lower_hull[-2], lower_hull[-1], point) <= 0:
                lower_hull.pop()
            lower_hull.append(point)

        return upper_hull[:-1] + lower_hull[:-1]

    convex_hull_points = convex_hull(points)
    number_of_hull_points = len(convex_hull_points)

    if number_of_hull_points < 3:
        return 0

    maximum_area = 0

    for i in range(number_of_hull_points):
        left_pointer = (i + 1) % number_of_hull_points
        right_pointer = (i + 2) % number_of_hull_points

        # Iterate through all possible combinations to maximize area.
        while True:
            area1 = calculate_area(convex_hull_points[i], convex_hull_points[left_pointer], convex_hull_points[right_pointer])
            next_right_pointer = (right_pointer + 1) % number_of_hull_points
            area2 = calculate_area(convex_hull_points[i], convex_hull_points[left_pointer], convex_hull_points[next_right_pointer])

            # Move right pointer if it leads to a bigger area.
            if area2 > area1:
                right_pointer = next_right_pointer
            else:
                maximum_area = max(maximum_area, area1)
                break
        
    return maximum_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list	Return 0, as no triangle can be formed.
Input list with fewer than 3 points	Return 0, as a triangle requires at least 3 points.
All points are collinear (lie on the same line)	Return 0, as a degenerate triangle has zero area.
Duplicate points in the input list	The area calculation formula will still work correctly; duplicates should not affect the maximum area found if they do not constitute one of the vertices of the maximum area triangle.
Integer overflow during area calculation with large coordinate values	Use a data type capable of holding larger values (e.g., long) or floating-point numbers (e.g., double) for the area calculation.
Floating-point precision issues when calculating area	Use a small tolerance value when comparing areas to account for potential floating-point inaccuracies.
Input list contains points with very large absolute coordinate values	Ensure that the chosen data types (e.g., int, long, double) can accommodate the range of coordinate values without overflow or loss of precision.
The three points that form the largest area triangle are close to being collinear	Floating-point imprecision might affect which triangle is identified, but should generally converge to correct area.

Empty input list

How to Handle:

Return 0, as no triangle can be formed.

Input list with fewer than 3 points

How to Handle:

Return 0, as a triangle requires at least 3 points.

All points are collinear (lie on the same line)

How to Handle:

Return 0, as a degenerate triangle has zero area.

Duplicate points in the input list

How to Handle:

The area calculation formula will still work correctly; duplicates should not affect the maximum area found if they do not constitute one of the vertices of the maximum area triangle.

Integer overflow during area calculation with large coordinate values

How to Handle:

Use a data type capable of holding larger values (e.g., long) or floating-point numbers (e.g., double) for the area calculation.

Floating-point precision issues when calculating area

How to Handle:

Use a small tolerance value when comparing areas to account for potential floating-point inaccuracies.

Input list contains points with very large absolute coordinate values

How to Handle:

Ensure that the chosen data types (e.g., int, long, double) can accommodate the range of coordinate values without overflow or loss of precision.

The three points that form the largest area triangle are close to being collinear

How to Handle:

Floating-point imprecision might affect which triangle is identified, but should generally converge to correct area.