Watch 5 video solutions for Find Maximum Area of a Triangle, a medium level problem involving Array, Hash Table, Math. This walkthrough by ExpertFunda has 529 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106coords[i] are unique.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.
| 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 |