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.
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; }}Video 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.