Watch 10 video solutions for Largest Triangle Area, a easy level problem involving Array, Math, Geometry. This walkthrough by codestorywithMIK has 6,966 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |