Largest Triangle Area: Brute Force with the Shoelace Formula

Given an array of points in the XY plane, return the area of the largest triangle that can be formed by any three of the points. The area is guaranteed to be greater than zero. That is LeetCode 812: Largest Triangle Area.

Example: points = [[0,0],[0,1],[1,0],[0,2],[2,0]] returns 2.0. The triangle formed by (0,0), (0,2), and (2,0) covers the most area.

Why this problem matters

Largest Triangle Area is a clean introduction to computational geometry. You need two things: a way to enumerate all candidate triangles, and a formula that computes a triangle's area from its vertices without measuring angles or heights. The Shoelace formula gives you that second piece, and it shows up again in problems about polygon area, convex hulls, and point-in-polygon tests.

The problem is rated easy because the input is small (at most 50 points) and brute force works perfectly. But the underlying math is worth learning. Once you know the Shoelace formula, you can apply it in harder geometry problems where efficiency matters more.

The approach: brute force with the Shoelace formula

Since we need the largest triangle out of all possible triples, we try every combination of three points and compute the area for each one. With at most 50 points, that is at most C(50,3) = 19,600 triples. That is fast.

The key tool is the Shoelace formula. Given three points (x1, y1), (x2, y2), (x3, y3), the area of the triangle they form is:

area = 0.5 * |x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)|

The absolute value handles the case where the points are ordered clockwise vs counterclockwise. If the three points are collinear, the formula returns zero, which is exactly right since collinear points do not form a triangle.

The algorithm:

1. Iterate over all triples (i, j, k) where i < j < k.
2. For each triple, compute the area using the Shoelace formula.
3. Track the maximum area seen.
4. Return the maximum.

The solution

def largest_triangle_area(points: list[list[int]]) -> float:
    n = len(points)
    best = 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]
                area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
                best = max(best, area)
    return best

Visual walkthrough

Let's trace through points = [[0,0],[0,1],[1,0],[0,2],[2,0]]. We evaluate several candidate triples, compute each area with the Shoelace formula, and keep the largest.

The triple A(0,0), D(0,2), E(2,0) produces area 2.0, which beats every other candidate. That is the answer.

Walkthrough of the code

Triple loop: The three nested loops with i < j < k enumerate every unique combination of three points without repetition or ordering duplicates. This is the standard way to iterate over C(n,3) combinations.

Shoelace computation: For each triple, we unpack the coordinates and plug them directly into the formula. The abs() call ensures the result is non-negative regardless of vertex ordering.

Tracking the best: We compare each area to the running maximum. Since the problem guarantees at least one valid triangle exists, best will be positive by the end.

Complexity analysis

Time: Three nested loops over n points give O(n^3). For n up to 50, this is about 20,000 iterations, well within limits.

Space: We only store a few scalar variables. The input array is not modified. Total: O(1) extra space.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

The Shoelace formula for triangle area

Computing the area of a triangle from three vertices using a single expression:

area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))

This formula avoids trigonometry, square roots, and distance calculations. It works in O(1) time and is numerically stable with integer or float coordinates. You will reuse it in convex hull problems, polygon area computations, and anywhere you need to check if three points are collinear (area equals zero means they are).

Enumerating all triples

The pattern of iterating over all C(n,3) combinations with three nested loops:

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            process(points[i], points[j], points[k])

This is the brute-force backbone for any problem that asks "find the best triple." You will see the same structure in problems like Valid Triangle Number (testing the triangle inequality on sorted side lengths) and Maximum Product of Three Numbers. The key is starting each inner loop at the previous index plus one, which avoids duplicate triples without needing a set.

Edge cases

• Three points: With exactly three points, there is only one possible triangle. Compute and return its area directly.
• Collinear triples: If three points lie on the same line, the Shoelace formula returns zero. This is handled naturally since zero will never beat a positive area.
• Duplicate points: If two or more points are identical, any triple containing duplicates produces zero area (a degenerate triangle). The algorithm handles this correctly.
• All points collinear: The problem guarantees the answer is greater than zero, so this case will not appear. But if it did, the algorithm would return 0.0.
• Negative coordinates: The absolute value in the Shoelace formula handles negative coordinates without any special cases.

From understanding to recall

You have seen how a triple loop combined with the Shoelace formula solves this problem in a few lines. The algorithm is simple, but the formula itself has subtle details: the cyclic structure of the terms, the absolute value, the 0.5 factor. Under time pressure, it is easy to mix up the signs or forget the absolute value.

Spaced repetition locks it in. You practice writing the Shoelace formula, the triple enumeration loop, and the collinearity check from scratch. Do it today, again in two days, again in five. After a few reps, you see "triangle area from coordinates" and the formula writes itself.

The Shoelace formula and triple enumeration are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Max Points on a Line: Slope Counting with GCD - Another geometry problem that processes all point pairs, using GCD-normalized slopes instead of area
• Erect the Fence: Convex Hull - Uses cross products and the Shoelace formula's underlying math to compute convex hulls
• Rectangle Area: Overlapping Geometry - Another computational geometry problem that computes area from coordinates

CodeBricks breaks Largest Triangle Area into its Shoelace formula and triple enumeration building blocks, then drills them independently with spaced repetition. You type the area computation, the nested loop structure, and the collinearity check from scratch until the pattern is automatic. When a geometry problem shows up in your interview, you do not think about it. You just write it.