Largest Triangle Area
EasyPrompt
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 <= 50- All the given points are unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible triangle that can be formed by the given points. It uses three nested loops to select three distinct points, calculates the area of the triangle they form, and keeps track of the maximum area found so far. This method is straightforward to implement and guarantees finding the correct answer by exhaustive search.
Algorithm
- Initialize a variable
maxAreato 0.0. - Use three nested loops to iterate through all unique combinations of three points
(p1, p2, p3)from the input arraypoints. - For each combination, calculate the area of the triangle formed by these three points. A common and efficient method is the Shoelace formula:
Area = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2))|. - Compare the calculated
currentAreawithmaxAreaand updatemaxAreaifcurrentAreais larger. - After checking all possible triplets,
maxAreawill hold the area of the largest triangle.
Walkthrough
The algorithm iterates through every unique triplet of points (i, j, k) using three nested loops, where i < j < k. This ensures that each combination of three points is considered exactly once. For each triplet points[i], points[j], and points[k], we calculate the area. The Shoelace formula is ideal for this, as it avoids complex trigonometric functions or square roots, relying only on the coordinates of the vertices. The formula is given by Area = 0.5 * |x_i(y_j - y_k) + x_j(y_k - y_i) + x_k(y_i - y_j)|. A running maximum maxArea is updated with the area of the current triangle if it's larger. Given the small constraint on the number of points (n <= 50), this cubic-time solution is perfectly feasible.
class Solution { public double largestTriangleArea(int[][] points) { int n = points.length; double maxArea = 0.0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { int[] p1 = points[i]; int[] p2 = points[j]; int[] p3 = points[k]; double area = 0.5 * Math.abs(p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])); maxArea = Math.max(maxArea, area); } } } return maxArea; }}Complexity
Time
O(n^3), where n is the number of points. The three nested loops lead to a cubic number of iterations.
Space
O(1) extra space, as we only need a few variables to store the coordinates and the maximum area.
Trade-offs
Pros
Very simple to understand and implement.
Requires no complex data structures or algorithms.
Sufficiently fast for the problem's constraints (n <= 50).
Cons
The time complexity of O(n^3) makes it inefficient for large datasets, although it's acceptable for the given constraints.
A more efficient, geometry-based approach relies on the fundamental property that the triangle with the largest area will have its vertices on the convex hull of the given points. This allows us to first reduce the problem to only the points on the hull and then use a specialized algorithm, known as 'rotating calipers', to find the largest triangle among these hull points in quadratic time.
Algorithm
- Step 1: Compute the Convex Hull. First, find the convex hull of the set of
npoints. An efficient algorithm like the Monotone Chain (takes O(n log n)) can be used. This gives a smaller set ofmpoints (m <= n) that form the vertices of the convex hull. - Step 2: Find the Largest Triangle on the Hull. The largest triangle must have its vertices on the convex hull. Instead of a naive O(m^3) check on the hull points, use the 'Rotating Calipers' algorithm, which finds the largest triangle in a convex polygon in O(m^2) time.
- The rotating calipers algorithm works by fixing one vertex
iand one side(i, j)of the hull. It then finds the third vertexkthat is farthest from the line segment(i, j). Asjadvances around the hull, the optimalkalso advances monotonically, allowing for an efficient O(m) scan for a fixedi. - By iterating
iover allmvertices, the total time for this step is O(m^2).
Walkthrough
This advanced approach consists of two main parts. First, we compute the convex hull of the input points. The Monotone Chain algorithm is a standard choice, which sorts the points and builds the hull in O(n log n) time. Let the number of vertices on the hull be m.
Second, we find the largest-area triangle whose vertices are chosen from the m hull points. A brute-force O(m^3) check is possible, but the optimal 'rotating calipers' technique achieves this in O(m^2). The algorithm fixes a base of the triangle, say (p_i, p_j), and efficiently finds the third vertex p_k that maximizes the triangle's area. The key insight is that as we 'rotate' the base by advancing j along the hull, the optimal third vertex k also moves monotonically. This avoids a full search for k for each new base, leading to the O(m^2) complexity.
The overall time complexity is O(n log n) for the hull computation plus O(m^2) for the rotating calipers part. Since m <= n, the total complexity is O(n^2).
// Note: The following is a conceptual representation. A full implementation// of Convex Hull and Rotating Calipers is non-trivial.class Solution { // Helper to calculate area private double area(int[] p1, int[] p2, int[] p3) { return 0.5 * Math.abs(p1[0] * (p2[1] - p3[1]) + p2[0] * (p3[1] - p1[1]) + p3[0] * (p1[1] - p2[1])); } public double largestTriangleArea(int[][] points) { // Step 1: Compute the convex hull of the points. // This would be a call to a function like `getConvexHull(points)`, // which implements an algorithm like Monotone Chain (O(n log n)). List<int[]> hull = getConvexHull(points); int m = hull.size(); if (m < 3) return 0.0; double maxArea = 0.0; // Step 2: Use Rotating Calipers to find the largest triangle on the hull (O(m^2)). for (int i = 0; i < m; i++) { int k = (i + 2) % m; for (int j = i + 1; j < m; j++) { int[] p_i = hull.get(i); int[] p_j = hull.get(j); // Find the farthest point k for the base (i, j). // The optimal k moves monotonically as j advances. while (true) { int next_k = (k + 1) % m; if (area(p_i, p_j, hull.get(next_k)) > area(p_i, p_j, hull.get(k))) { k = next_k; } else { break; } } maxArea = Math.max(maxArea, area(p_i, p_j, hull.get(k))); } } return maxArea; } // A full implementation of a convex hull algorithm (e.g., Monotone Chain) // would be required here. It's omitted for brevity. private List<int[]> getConvexHull(int[][] points) { // ... O(n log n) implementation ... // Returns a list of points on the hull in counter-clockwise order. // For this example, we'll just use all points to make it runnable, // though this defeats the purpose of the optimization. Arrays.sort(points, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); List<int[]> hull = new ArrayList<>(); // Lower hull for (int[] p : points) { while (hull.size() >= 2 && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) <= 0) { hull.remove(hull.size() - 1); } hull.add(p); } // Upper hull int lowerHullSize = hull.size(); for (int i = points.length - 2; i >= 0; i--) { int[] p = points[i]; while (hull.size() > lowerHullSize && crossProduct(hull.get(hull.size() - 2), hull.get(hull.size() - 1), p) <= 0) { hull.remove(hull.size() - 1); } hull.add(p); } hull.remove(hull.size() - 1); // Remove duplicate start point return hull; } private int crossProduct(int[] p1, int[] p2, int[] p3) { return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]); }}Complexity
Time
O(n^2). The convex hull calculation is O(n log n), and the rotating calipers algorithm on the `m` hull points is O(m^2). Since `m <= n`, the total complexity is O(n^2).
Space
O(n) to store the points on the convex hull.
Trade-offs
Pros
Asymptotically faster with O(n^2) time complexity.
Much more scalable for larger numbers of points.
Cons
Significantly more complex to implement correctly.
Requires knowledge of computational geometry algorithms (Convex Hull, Rotating Calipers).
The performance gain is not critical for the given small constraints, making the implementation effort potentially unnecessary.
Solutions
Solution
class Solution {public double largestTriangleArea(int[][] points) { double ans = 0; for (int[] p1 : points) { int x1 = p1[0], y1 = p1[1]; for (int[] p2 : points) { int x2 = p2[0], y2 = p2[1]; for (int[] p3 : points) { int x3 = p3[0], y3 = p3[1]; int u1 = x2 - x1, v1 = y2 - y1; int u2 = x3 - x1, v2 = y3 - y1; double t = Math.abs(u1 * v2 - u2 * v1) / 2.0; ans = Math.max(ans, t); } } } return ans; }}class Solution {public: double largestTriangleArea(vector<vector<int>> &points) { double ans = 0; for (auto &p1 : points) { int x1 = p1[0], y1 = p1[1]; for (auto &p2 : points) { int x2 = p2[0], y2 = p2[1]; for (auto &p3 : points) { int x3 = p3[0], y3 = p3[1]; int u1 = x2 - x1, v1 = y2 - y1; int u2 = x3 - x1, v2 = y3 - y1; double t = abs(u1 * v2 - u2 * v1) / 2.0; ans = max(ans, t); } } } return ans; }};class Solution: def largestTriangleArea(self, points: List[List[int]]) -> float: ans = 0 for x1, y1 in points: for x2, y2 in points: for x3, y3 in points: u1, v1 = x2 - x1, y2 - y1 u2, v2 = x3 - x1, y3 - y1 t = abs(u1 * v2 - u2 * v1) / 2 ans = max(ans, t) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.