LeetCode 812: Largest Triangle Area

Problem Restatement

We are given an array of unique points on the X-Y plane.

Each point is written as:

[x, y]

We need to choose any three different points and form a triangle.

Return the largest possible triangle area.

Answers within 10^-5 of the actual answer are accepted. The constraints are small: 3 <= points.length <= 50, and each coordinate is between -50 and 50.

Input and Output

Examples

Example 1:

points = [[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]

The largest triangle can be formed by:

[0, 0], [0, 2], [2, 0]

This is a right triangle with base 2 and height 2, so its area is:

2.0

The answer is:

2.00000

Example 2:

points = [[1, 0], [0, 0], [0, 1]]

These three points form a right triangle with base 1 and height 1.

The area is:

0.5

The answer is:

0.50000

First Thought: Check Every Triangle

There are at most 50 points.

The number of ways to choose three points is:

C(50, 3) = 19600

That is small enough.

So we can enumerate every triplet of points, compute its area, and keep the maximum.

Key Insight

We do not need distances, angles, or square roots.

For three points:

A = (x1, y1)
B = (x2, y2)
C = (x3, y3)

The area of the triangle is half the absolute value of the 2D cross product:

abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2

The cross product gives the signed area of the parallelogram formed by vectors AB and AC. A triangle is half of that parallelogram.

If the three points are collinear, the cross product is 0, so the area is 0.

Algorithm

Initialize:

best = 0.0

Loop over all triplets of points:

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):

For each triplet:

1. Let the points be A, B, and C.
2. Compute the triangle area using the cross product formula.
3. Update best if this area is larger.

Return best.

Correctness

The algorithm considers every possible choice of three different points because the three nested loops enumerate all index triples i < j < k.

For each such triple, the cross product formula computes the exact area of the triangle formed by those three points. The absolute value handles orientation, so the result is always non-negative.

The variable best is updated with the maximum area seen so far. After all triples have been processed, every valid triangle has been considered, and best is the largest area among them.

Therefore, the algorithm returns the required largest triangle area.

Complexity

Let n = len(points).

With n <= 50, this is easily fast enough.

Implementation

class Solution:
    def largestTriangleArea(self, points: list[list[int]]) -> float:
        def area(a: list[int], b: list[int], c: list[int]) -> float:
            x1, y1 = a
            x2, y2 = b
            x3, y3 = c

            return abs(
                (x2 - x1) * (y3 - y1)
                - (x3 - x1) * (y2 - y1)
            ) / 2

        n = len(points)
        best = 0.0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    best = max(best, area(points[i], points[j], points[k]))

        return best

Code Explanation

The helper function extracts the coordinates:

x1, y1 = a
x2, y2 = b
x3, y3 = c

Then it computes the area using the determinant form of the cross product:

abs(
    (x2 - x1) * (y3 - y1)
    - (x3 - x1) * (y2 - y1)
) / 2

The absolute value is needed because the sign depends on the order of the points.

The loops choose every distinct triplet once:

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):

Each area is compared with the current best answer:

best = max(best, area(points[i], points[j], points[k]))

Finally, best is returned.

Testing

def close(a, b, eps=1e-5):
    return abs(a - b) <= eps

def run_tests():
    s = Solution()

    assert close(
        s.largestTriangleArea([[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]),
        2.0,
    )

    assert close(
        s.largestTriangleArea([[1, 0], [0, 0], [0, 1]]),
        0.5,
    )

    assert close(
        s.largestTriangleArea([[0, 0], [1, 1], [2, 2]]),
        0.0,
    )

    assert close(
        s.largestTriangleArea([[-1, 0], [1, 0], [0, 2], [0, -2]]),
        4.0,
    )

    print("all tests passed")

run_tests()