Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

With at most 50 points, every triple can be considered directly. The reference solutions calculate the three side lengths and use Heron's formula, which gives a triangle's area from its sides without needing to choose a base or altitude.

Approach

Enumerate indices i < j < k, so every three-point choice is evaluated exactly once.
Compute the Euclidean lengths a, b, and c between the three point pairs.
Let s = (a + b + c) / 2. The area is the square root of s * (s - a) * (s - b) * (s - c). Clamp this product to at least zero before taking its square root.
Return the largest computed area.

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        res = float('-inf')

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    x1, y1 = points[i]
                    x2, y2 = points[j]
                    x3, y3 = points[k]
                    a = sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)
                    b = sqrt(abs(x2 - x3) ** 2 + abs(y2 - y3) ** 2)
                    c = sqrt(abs(x1 - x3) ** 2 + abs(y1 - y3) ** 2)
                    sp = (a + b + c) / 2
                    val = sp * (sp - a) * (sp - b) * (sp - c)
                    area = sqrt(max(0, val))
                    res = max(res, area)

        return res

Complexity analysis

For n points, the three nested loops examine every triple, taking O(n³) time and O(1) auxiliary space.