Find Maximum Area of a Triangle - Solution & Explanation

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.