Difficulty: 🟢 Easy
Topics: Array, Math, Geometry

Solution

LeetCode 812, Largest Triangle Area

Problem Understanding

The problem gives us a list of unique points on a 2D X-Y plane. Each point is represented as a pair of integers [x, y]. Our task is to choose any three distinct points and compute the area of the triangle formed by those points. Among all possible triangles, we must return the largest area.

A triangle in a 2D plane can be uniquely determined by any three non-collinear points. If the three chosen points lie on the same straight line, then the triangle area is 0, because no actual triangle exists in that case.

The input size is relatively small:

3 <= points.length <= 50
Coordinates range from -50 to 50
All points are unique

These constraints are important because they tell us that a brute-force solution is completely feasible. With at most 50 points, the total number of ways to choose 3 points is:

$$\binom{50}{3} = 19600$$

This is a very manageable number for modern computers.

The expected output is a floating point number representing the maximum triangle area. The problem accepts answers within 10^-5, so small floating point precision differences are acceptable.

There are several important edge cases to keep in mind:

Some sets of three points may be collinear, producing area 0
Coordinates can be negative, so the area formula must correctly handle signed values
Multiple triangles may have the same maximum area
The minimum input size is exactly three points, meaning the answer may simply be the area of that single triangle

Approaches

Brute Force Approach

The brute-force solution checks every possible combination of three distinct points.

For each triple (A, B, C), we compute the area of the triangle formed by those points. We keep track of the maximum area seen so far and return it at the end.

The standard geometry formula for the area of a triangle using coordinates is:

$$\text{Area} = \frac{1}{2} \left| x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2) \right|$$

This formula comes from the determinant of vectors and is often called the Shoelace Formula for triangles.

Because we examine every possible triangle exactly once, this approach is guaranteed to find the largest area.

The brute-force solution is actually efficient enough for the given constraints because there are at most 19,600 triangles to evaluate.

Optimal Approach

The optimal approach is effectively the same as the brute-force method because the constraints are small enough that checking all triples is already efficient.

The key insight is that triangle area computation is constant time. Since:

$$O\left(\binom{n}{3}\right) = O(n^3)$$

and n <= 50, the total work remains very small.

There is no need for advanced computational geometry optimizations such as convex hulls or rotating calipers because the input size does not justify the additional complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triangle
Optimal	O(n³)	O(1)	Same approach, already efficient enough for constraints

Algorithm Walkthrough

Initialize a variable called max_area to 0.0.

This variable stores the largest triangle area found so far. 2. Iterate through every possible triple of distinct points.

Use three nested loops:

The first loop selects the first point
The second loop selects the second point
The third loop selects the third point

By carefully choosing loop ranges, we ensure every combination is visited exactly once. 3. For each triple of points, compute the triangle area.

Suppose the three points are:

$$(x_1, y_1), (x_2, y_2), (x_3, y_3)$$

The area is:

$\text{Area} = \frac{1}{2}\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|$

The absolute value is necessary because the determinant may be negative depending on point ordering. 4. Compare the computed area with max_area.

If the current area is larger, update max_area. 5. After all triples have been processed, return max_area.

Why it works

The algorithm examines every possible set of three distinct points. Every valid triangle that can be formed from the input appears in exactly one iteration of the loops. Since we compute the exact area for each triangle and track the maximum value, the final result must be the largest possible triangle area.

Python Solution

from typing import List

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def triangle_area(p1: List[int], p2: List[int], p3: List[int]) -> float:
            x1, y1 = p1
            x2, y2 = p2
            x3, y3 = p3

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

        n = len(points)
        max_area = 0.0

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

        return max_area

The implementation begins by defining a helper function called triangle_area. This function extracts the coordinates from the three points and applies the determinant-based area formula.

The main method stores the number of points in n and initializes max_area to 0.0.

The three nested loops generate every unique combination of three points. The loop structure ensures that:

i < j < k
No point is reused
No combination is repeated

For every triangle, the area is computed and compared against the current maximum.

Finally, the largest area discovered during iteration is returned.

Go Solution

import "math"

func largestTriangleArea(points [][]int) float64 {
    triangleArea := func(p1, p2, p3 []int) float64 {
        x1, y1 := p1[0], p1[1]
        x2, y2 := p2[0], p2[1]
        x3, y3 := p3[0], p3[1]

        area := float64(
            x1*(y2-y3) +
                x2*(y3-y1) +
                x3*(y1-y2),
        )

        return math.Abs(area) / 2.0
    }

    n := len(points)
    maxArea := 0.0

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                area := triangleArea(points[i], points[j], points[k])

                if area > maxArea {
                    maxArea = area
                }
            }
        }
    }

    return maxArea
}

The Go solution follows the same logic as the Python implementation.

One notable difference is that Go requires explicit conversion to float64 before using floating point operations. The math.Abs function is also used to compute the absolute value safely.

Slices are used for point storage, and indexing accesses the x and y coordinates directly.

Because coordinate values are small, integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input:

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

Let the points be:

Index	Point
0	(0,0)
1	(0,1)
2	(1,0)
3	(0,2)
4	(2,0)

The algorithm checks all possible triples.

Triangle	Area
(0,0), (0,1), (1,0)	0.5
(0,0), (0,1), (0,2)	0
(0,0), (0,1), (2,0)	1
(0,0), (1,0), (0,2)	1
(0,0), (0,2), (2,0)	2
(0,1), (1,0), (2,0)	0.5

The largest area found is:

$$2.0$$

So the final answer is:

2.00000

Example 2

Input:

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

There is only one possible triangle.

Using the formula:

$$\text{Area} = \frac{ |1(0-1) + 0(1-0) + 0(0-0)| }{2}$$

$$= \frac{| -1 |}{2} = 0.5$$

Output:

0.50000

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	Three nested loops iterate through all point triples
Space	O(1)	Only a few variables are used

The algorithm evaluates every combination of three points. Since there are approximately n³ / 6 such combinations, the runtime complexity is cubic.

The memory usage remains constant because no additional data structures proportional to the input size are created.

Test Cases

from typing import List

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        def triangle_area(p1, p2, p3):
            x1, y1 = p1
            x2, y2 = p2
            x3, y3 = p3

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

        n = len(points)
        max_area = 0.0

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

        return max_area

solution = Solution()

assert solution.largestTriangleArea(
    [[0,0],[0,1],[1,0],[0,2],[2,0]]
) == 2.0  # Provided example with largest area 2

assert solution.largestTriangleArea(
    [[1,0],[0,0],[0,1]]
) == 0.5  # Minimum valid triangle

assert solution.largestTriangleArea(
    [[0,0],[1,1],[2,2]]
) == 0.0  # Collinear points produce zero area

assert solution.largestTriangleArea(
    [[-1,0],[0,1],[1,0],[0,-1]]
) == 1.0  # Negative coordinates

assert solution.largestTriangleArea(
    [[0,0],[5,0],[0,5],[1,1]]
) == 12.5  # Large right triangle

assert solution.largestTriangleArea(
    [[0,0],[2,0],[1,3],[1,1]]
) == 3.0  # Interior point should not affect maximum

assert solution.largestTriangleArea(
    [[50,50],[-50,-50],[50,-50]]
) == 5000.0  # Boundary coordinate values

Test	Why
`[[0,0],[0,1],[1,0],[0,2],[2,0]]`	Validates the provided example
`[[1,0],[0,0],[0,1]]`	Tests minimum input size
`[[0,0],[1,1],[2,2]]`	Verifies collinear handling
`[[-1,0],[0,1],[1,0],[0,-1]]`	Ensures negative coordinates work correctly
`[[0,0],[5,0],[0,5],[1,1]]`	Tests larger triangle areas
`[[0,0],[2,0],[1,3],[1,1]]`	Confirms interior points do not affect result
`[[50,50],[-50,-50],[50,-50]]`	Tests boundary coordinate constraints

Edge Cases

One important edge case occurs when all points are collinear. In this situation, every possible triangle has area 0. A buggy implementation might incorrectly return a negative value or fail because it assumes every triple forms a valid triangle. This implementation handles the case naturally because the determinant formula evaluates to 0 for collinear points.

Another important case involves negative coordinates. Geometry formulas sometimes fail when sign handling is incorrect. The determinant used for triangle area may produce either a positive or negative value depending on point ordering. By applying abs(), the implementation guarantees the area is always non-negative.

A third edge case is the minimum input size of exactly three points. In this scenario, there is only one possible triangle. Some implementations accidentally assume multiple combinations exist or initialize loops incorrectly. The nested loop structure here correctly evaluates the single available triangle and returns its area.

A final edge case involves duplicate computation of the same triangle. If the loops are not carefully structured, the algorithm may evaluate permutations of the same three points multiple times. Using the condition i < j < k guarantees every triangle is processed exactly once.

LeetCode 812 - Largest Triangle Area