Difficulty: Easy | Acceptance: 71.60% | Paid: No Topics: Array, Math, Geometry
You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.
Example: Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] Output: 2.00000 Explanation: The five points are shown in the figure. The red triangle is the largest.
Table of Contents
- Examples
- Constraints
- Brute Force (Shoelace Formula)
- Convex Hull + Rotating Calipers
Examples
Example 1
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are show in the 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.
Brute Force (Shoelace Formula)
Intuition Since the number of points is small (N ≤ 50), we can check every possible combination of 3 points. The area of a triangle formed by three points can be calculated efficiently using the Shoelace formula (or the determinant method).
Steps
- Iterate through all unique triplets of points using three nested loops.
- For each triplet (A, B, C), calculate the area using the formula: $0.5 \times |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|$.
- Keep track of the maximum area found.
class Solution:
def largestTriangleArea(self, points: list[list[int]]) -> float:
n = len(points)
max_area = 0.0
for i in range(n):
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
for k in range(j + 1, n):
x3, y3 = points[k]
# Shoelace formula / Cross product magnitude
area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0
max_area = max(max_area, area)
return max_area
Complexity
- Time: O(N³) — We iterate through all combinations of 3 points.
- Space: O(1) — We only store variables for coordinates and max area.
- Notes: This is the simplest approach and is very efficient given the constraint N ≤ 50.
Convex Hull + Rotating Calipers
Intuition The largest triangle must have its vertices on the convex hull of the point set. We can first compute the convex hull (e.g., using Monotone Chain), then use a rotating calipers technique to find the maximum area triangle in O(M²) or O(M) time, where M is the number of points on the hull.
Steps
- Compute the Convex Hull of the points.
- If the hull has fewer than 3 points, return 0.
- Iterate through each pair of points on the hull (i, j).
- For each pair (i, j), find the point k on the hull that maximizes the area of the triangle (i, j, k). Since the hull is convex, as we move j forward, k will also move forward (monotonicity).
- Track the maximum area found.
class Solution:
def largestTriangleArea(self, points: list[list[int]]) -> float:
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
points.sort()
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
hull = lower[:-1] + upper[:-1]
n = len(hull)
if n < 3:
return 0.0
max_area = 0.0
for i in range(n):
k = i + 2
for j in range(i + 1, n):
while k + 1 < n and cross(hull[i], hull[j], hull[k]) < cross(hull[i], hull[j], hull[k+1]):
k += 1
area = abs(cross(hull[i], hull[j], hull[k])) / 2.0
max_area = max(max_area, area)
return max_area
Complexity
- Time: O(N log N + M²) — Sorting takes O(N log N). Finding the convex hull takes O(N). Finding the max area triangle on the hull takes O(M²) where M is the number of points on the hull.
- Space: O(N) — To store the convex hull.
- Notes: This approach is optimal for larger datasets where N is large, but for N ≤ 50, the brute force method is simpler and equally fast.