Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] Output: 2.00000 Explanation: The five points are shown in the above figure. The red triangle is the largest.
Example 2:
Input: points = [[1,0],[0,0],[0,1]] Output: 0.50000
Constraints:
3 <= points.length <= 50-50 <= xi, yi <= 50Problem Overview: You are given a list of 2D points on a plane. The task is to choose any three distinct points that form a triangle with the maximum possible area. If multiple triangles exist, return the largest area among them.
Approach 1: Brute Force Using Determinant Formula (Time: O(n^3), Space: O(1))
The direct method checks every possible combination of three points. Use three nested loops to iterate through triplets (i, j, k). For each triplet, compute the triangle's area using the determinant-based formula: area = |x1(y2−y3) + x2(y3−y1) + x3(y1−y2)| / 2. This formula comes from coordinate geometry and works for any orientation of points. Track the maximum area seen during iteration. Since every combination must be examined, the runtime is O(n^3), but the implementation is straightforward and uses constant extra space.
This approach works well because the constraint sizes are small enough that enumerating all triangles is feasible. The determinant formula avoids computing side lengths or using Heron's formula, keeping the computation simple and numerically stable.
Approach 2: Optimized Formulaic Approach Using Shoelace Formula (Time: O(n^3), Space: O(1))
The Shoelace formula provides a clean way to compute the area of a polygon using coordinates. For a triangle with vertices (x1,y1), (x2,y2), and (x3,y3), the area becomes 0.5 * |x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3|. The algorithm still iterates through all combinations of three points from the array of coordinates, but the calculation step becomes a single expression derived from the Shoelace rule used in computational math.
This formula avoids intermediate steps and expresses the triangle area directly in terms of cross products of coordinates. The runtime remains O(n^3) because the number of point triplets dominates the cost. Space complexity stays O(1) since only a few numeric variables are used while scanning the combinations.
Recommended for interviews: Interviewers typically expect the brute-force combination approach combined with a correct geometric area formula. Enumerating all point triplets demonstrates that you understand the search space, while applying the determinant or Shoelace formula shows familiarity with coordinate geometry. The key is recognizing that triangle area can be computed directly from coordinates without calculating side lengths.
This approach considers every combination of three points and calculates the area using the determinant formula for the area of a triangle. Given three points (x1, y1), (x2, y2), (x3, y3), the area A can be computed as:
A = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|
We iterate over all combinations of three points, calculate the area for each, and keep track of the maximum area encountered.
We define a helper function calculateArea that takes three points and computes the area of the triangle formed by these points using the determinant formula. The main function iterates through all combinations of three points and calculates the area, updating the maximum if a larger area is found.
Time Complexity: O(n^3), where n is the number of points as we check every combination of three points.
Space Complexity: O(1), as we are only using a constant amount of extra space.
This approach also solves the problem using the Shoelace formula (an efficacious method for calculating the area of a polygon). While typically useful for polygons, here we can apply it to triangles. Given three points (x1, y1), (x2, y2), and (x3, y3), the triangle area A is:
A = 0.5 * |x1y2 + x2y3 + x3y1 - y1x2 - y2x3 - y3x1|
While this is similar to the determinant approach, it clarifies computational steps explicitly and can be implemented directly.
The C version uses the Shoelace theorem by simply formalizing it in a helper function calculateArea. It considers all triplets and records the largest valid area, returning it.
Time Complexity: O(n^3); still involves three nested loops.
Space Complexity: O(1); no extra space beyond simple counters.
Given three points (x_1, y_1), (x_2, y_2), (x_3, y_3) on a plane, the area formula is:
$S = \frac{1}{2} \left| x_1y_2 + x_2y_3 + x_3y_1 - x_1y_3 - x_2y_1 - x_3y_2 \right|
We can enumerate all combinations of three points and calculate the maximum area.
The time complexity is O(n^3), where n is the number of points. The space complexity is O(1)$.
| Approach | Complexity |
|---|---|
| Brute Force Approach using Determinant Formula | Time Complexity: O(n^3), where n is the number of points as we check every combination of three points. |
| Optimized Formulaic ApproachUsing Shoelace Formula | Time Complexity: O(n^3); still involves three nested loops. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Using Determinant Formula | O(n^3) | O(1) | Simple implementation when constraints allow checking all point triplets |
| Shoelace Formula Iteration | O(n^3) | O(1) | Cleaner coordinate-based area calculation in geometry-heavy problems |
Largest Triangle Area | Heron | Shoelace | Leetcode 812 | codestorywithMIK • codestorywithMIK • 6,966 views views
Watch 9 more video solutions →Practice Largest Triangle Area with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor