Find Maximum Area of a Triangle solution and explanation
Google
2 more videos on this problem
Leetcode 3588: Find Maximum Area of a Triangle | Java + Intuition + Dry Run | Biweekly Contest 159ExpertFunda · 19:38 · 564 views
3588. Find Maximum Area of a Triangle (Leetcode Medium)Programming Live with Larry · 16:42 · 529 views
Leetcode 3588. Find Maximum Area of a Triangle | Set | Map | Medium | O(NLogN)Leet's Code · 30:20 · 370 views
The problem
You are given a 2D array coords of size n x 2, representing the coordinates of n points in an infinite Cartesian plane.
Find twice the maximum area of a triangle with its corners at any three elements from coords, such that at least one side of this triangle is parallel to the x-axis or y-axis. Formally, if the maximum area of such a triangle is A, return 2 * A.
If no such triangle exists, return -1.
Note that a triangle cannot have zero area.
Example 1:
Input: coords = [[1,1],[1,2],[3,2],[3,3]]
Output: 2
Explanation:
The triangle shown in the image has a base 1 and height 2. Hence its area is 1/2 * base * height = 1.
Example 2:
Input: coords = [[1,1],[2,2],[3,3]]
Output: -1
Explanation:
The only possible triangle has corners (1, 1), (2, 2), and (3, 3). None of its sides are parallel to the x-axis or the y-axis.
Constraints:
1 <= n == coords.length <= 1051 <= coords[i][0], coords[i][1] <= 106- All
coords[i]are unique.
Approach overview
Problem Overview: You are given a set of points on a 2D grid. The task is to choose three points that form a triangle with the maximum possible area. If no valid triangle exists, return 0. The core challenge is evaluating combinations efficiently without recomputing geometric properties repeatedly.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
The most direct solution checks every combination of three points. For each triplet (i, j, k), compute the triangle area using the shoelace formula: area = |x1(y2−y3) + x2(y3−y1) + x3(y1−y2)| / 2. Track the maximum area across all triplets. This approach guarantees correctness because it evaluates every possible triangle, but the triple nested loop leads to O(n^3) time. It becomes slow once the number of points grows beyond a few hundred.
Approach 2: Enumeration + Hash Map (O(n^2) time, O(n) space)
You can reduce redundant geometric work by precomputing coordinate extremes. Use a hash table keyed by x or y coordinate to store the minimum and maximum values observed along the other axis. While enumerating pairs of points as a potential base, you can quickly look up the farthest third point that maximizes the triangle height using constant-time hash lookups. This transforms the expensive third loop into a lookup operation.
The insight comes from triangle geometry: for a fixed base, the area depends only on the perpendicular distance (height) of the third point. By storing coordinate extremes in a map, you avoid scanning all remaining points to find the maximum height. The algorithm still enumerates candidate bases in O(n^2), but determining the best third vertex becomes O(1). Total complexity becomes O(n^2) time and O(n) extra space.
This strategy mixes geometry with array enumeration. The hash structure stores geometric constraints, while the pair iteration evaluates candidate bases.
Recommended for interviews: Start with the brute force triplet enumeration to show you understand the geometric area formula. Then optimize by introducing the hash map that stores coordinate extremes. Interviewers typically expect the O(n^2) enumeration + hash map approach because it demonstrates awareness of geometric properties and efficient lookup structures.
Solution
The problem asks for twice the area of the triangle, so we can directly calculate the product of the base and height of the triangle.
Since the triangle must have at least one side parallel to the x-axis or y-axis, we can enumerate sides parallel to the x-axis and calculate the double area for all possible triangles, then swap the coordinates in coords and repeat the process to calculate the double area for triangles with sides parallel to the y-axis.
Therefore, we design a function calc to calculate the double area for all possible triangles with sides parallel to the y-axis.
We use two hash maps f and g to record the minimum and maximum y-coordinates for each x-coordinate. Then we iterate through coords, updating f and g, and also record the minimum and maximum x-coordinates. Finally, we iterate through f, calculate the double area for each x-coordinate, and update the answer.
In the main function, we first call the calc function to calculate the double area for triangles with sides parallel to the y-axis, then swap the coordinates in coords and repeat the process to calculate the double area for triangles with sides parallel to the x-axis. Finally, we return the answer; if the answer is 0, we return -1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of coords.
class Solution:
def maxArea(self, coords: List[List[int]]) -> int:
def calc() -> int:
mn, mx = inf, 0
f = {}
g = {}
for x, y in coords:
mn = min(mn, x)
mx = max(mx, x)
if x in f:
f[x] = min(f[x], y)
g[x] = max(g[x], y)
else:
f[x] = g[x] = y
ans = 0
for x, y in f.items():
d = g[x] - y
ans = max(ans, d * max(mx - x, x - mn))
return ans
ans = calc()
for c in coords:
c[0], c[1] = c[1], c[0]
ans = max(ans, calc())
return ans if ans else -1class Solution {
public long maxArea(int[][] coords) {
long ans = calc(coords);
for (int[] c : coords) {
int tmp = c[0];
c[0] = c[1];
c[1] = tmp;
}
ans = Math.max(ans, calc(coords));
return ans > 0 ? ans : -1;
}
private long calc(int[][] coords) {
int mn = Integer.MAX_VALUE, mx = 0;
Map<Integer, Integer> f = new HashMap<>();
Map<Integer, Integer> g = new HashMap<>();
for (int[] c : coords) {
int x = c[0], y = c[1];
mn = Math.min(mn, x);
mx = Math.max(mx, x);
if (f.containsKey(x)) {
f.put(x, Math.min(f.get(x), y));
g.put(x, Math.max(g.get(x), y));
} else {
f.put(x, y);
g.put(x, y);
}
}
long ans = 0;
for (var e : f.entrySet()) {
int x = e.getKey();
int y = e.getValue();
int d = g.get(x) - y;
ans = Math.max(ans, (long) d * Math.max(mx - x, x - mn));
}
return ans;
}
}class Solution {
public:
long long maxArea(vector<vector<int>>& coords) {
auto calc = [&]() -> long long {
int mn = INT_MAX, mx = 0;
unordered_map<int, int> f, g;
for (auto& c : coords) {
int x = c[0], y = c[1];
mn = min(mn, x);
mx = max(mx, x);
if (f.count(x)) {
f[x] = min(f[x], y);
g[x] = max(g[x], y);
} else {
f[x] = y;
g[x] = y;
}
}
long long ans = 0;
for (auto& [x, y] : f) {
int d = g[x] - y;
ans = max(ans, 1LL * d * max(mx - x, x - mn));
}
return ans;
};
long long ans = calc();
for (auto& c : coords) {
swap(c[0], c[1]);
}
ans = max(ans, calc());
return ans > 0 ? ans : -1;
}
};function maxArea(coords: number[][]): number {
function calc(): number {
let [mn, mx] = [Infinity, 0];
const f = new Map<number, number>();
const g = new Map<number, number>();
for (const [x, y] of coords) {
mn = Math.min(mn, x);
mx = Math.max(mx, x);
if (f.has(x)) {
f.set(x, Math.min(f.get(x)!, y));
g.set(x, Math.max(g.get(x)!, y));
} else {
f.set(x, y);
g.set(x, y);
}
}
let ans = 0;
for (const [x, y] of f) {
const d = g.get(x)! - y;
ans = Math.max(ans, d * Math.max(mx - x, x - mn));
}
return ans;
}
let ans = calc();
for (const c of coords) {
[c[0], c[1]] = [c[1], c[0]];
}
ans = Math.max(ans, calc());
return ans > 0 ? ans : -1;
}func maxArea(coords [][]int) int64 {
calc := func() int64 {
mn, mx := int(1e9), 0
f := make(map[int]int)
g := make(map[int]int)
for _, c := range coords {
x, y := c[0], c[1]
mn = min(mn, x)
mx = max(mx, x)
if _, ok := f[x]; ok {
f[x] = min(f[x], y)
g[x] = max(g[x], y)
} else {
f[x] = y
g[x] = y
}
}
var ans int64
for x, y := range f {
d := g[x] - y
ans = max(ans, int64(d)*int64(max(mx-x, x-mn)))
}
return ans
}
ans := calc()
for _, c := range coords {
c[0], c[1] = c[1], c[0]
}
ans = max(ans, calc())
if ans > 0 {
return ans
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Enumeration | O(n^3) | O(1) | Small inputs or when implementing the simplest correct solution first |
| Enumeration + Hash Map | O(n^2) | O(n) | General case optimization when many points exist and repeated scans must be avoided |
Frequently asked questions
Is Find Maximum Area of a Triangle easy or hard?
This problem is typically rated Medium difficulty. The brute force idea is straightforward, but identifying how to reduce the third loop using coordinate extremes and a hash map requires understanding geometry and optimization patterns.
Find Maximum Area of a Triangle Python/Java solution
Most implementations iterate through pairs of points and use a hash map to quickly determine the farthest valid third point. The logic is identical across languages such as Python, Java, C++, Go, and TypeScript. Each version computes triangle area using a geometry formula while leveraging O(1) hash lookups.
How to solve Find Maximum Area of a Triangle in O(n^2)?
Enumerate pairs of points as a potential triangle base. Precompute minimum and maximum coordinates using a hash table so the farthest third point can be retrieved instantly. The triangle area depends on base length and perpendicular height, so the lookup provides the maximum height in O(1) time while the base enumeration takes O(n^2).
What is the best approach for Find Maximum Area of a Triangle?
The most practical approach uses enumeration combined with a hash map that stores coordinate extremes. Instead of checking every possible third point for a base, the map allows constant-time lookup of the farthest candidate. This reduces the complexity from O(n^3) brute force to O(n^2) time with O(n) extra space.
Is Find Maximum Area of a Triangle asked at Google/Amazon/Meta?
Geometry and enumeration problems involving maximum area or coordinate extremes frequently appear in interviews at companies like Amazon, Google, and Meta. Variants often combine geometric formulas with hash tables or greedy observations to reduce brute force complexity.
What data structure is used in Find Maximum Area of a Triangle?
A hash table is commonly used to store coordinate extremes such as the minimum and maximum values for a given x or y coordinate. This allows constant-time lookups when evaluating candidate triangle bases, making the optimized approach significantly faster than pure enumeration.
What is the time complexity of Find Maximum Area of a Triangle?
The brute force approach checks every triplet of points and runs in O(n^3) time. The optimized enumeration + hash map solution reduces the complexity to O(n^2) by replacing the third loop with constant-time lookups. Space complexity is O(n) for storing coordinate extremes.