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 <= 50In #812 Largest Triangle Area, you are given a set of 2D points and must determine the largest possible area of a triangle formed by any three of them. Since a triangle is defined by exactly three points, the key idea is to evaluate combinations of three points and compute the area for each candidate triangle.
A common geometric technique is the shoelace formula or the cross product. For three points (x1, y1), (x2, y2), and (x3, y3), the triangle area can be computed using the determinant-based formula: area = |x1(y2−y3) + x2(y3−y1) + x3(y1−y2)| / 2. By iterating through every combination of three points and tracking the maximum area encountered, you can determine the result.
This brute-force geometric approach works efficiently because the number of points is relatively small. The algorithm mainly relies on nested iteration and constant-time area computation. Careful use of absolute values ensures correct area calculation regardless of point orientation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Check all triplets using geometric area formula | O(n^3) | O(1) |
Sahil & Sarra
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry-based array problems like this sometimes appear in coding interviews. They test understanding of coordinate geometry, nested iteration, and mathematical formulas.
A simple array or list of coordinate pairs is sufficient. The algorithm mainly iterates over combinations of points, so no advanced data structures are required.
The typical approach is to check every combination of three points and compute the triangle area using the shoelace formula or cross product. Since the number of points is small, this brute-force strategy is efficient and easy to implement.
Most solutions use the shoelace formula or the cross product method. Both compute the area of a triangle formed by three coordinate points using determinant-based geometry calculations.