Largest Triangle Area

main.md

Question

Approach

Brute force way. I iterate over all combinations of three distinct points (since (n \le 50) this (O(n^3)) brute-force is fine). For each triple I compute the triangle area using the cross product formula: for points (A(x_1,y_1), B(x_2,y_2), C(x_3,y_3)) the area is (\tfrac{1}{2}\big| (x_2-x_1)(y_3-y_1) - (x_3-x_1)(y_2-y_1)\big|). I track the maximum area seen and return it.

Implementation

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        max_area = 0.0
        for (x1, y1), (x2, y2), (x3, y3) in itertools.combinations(points, 3):
            cross = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
            area = abs(cross) / 2.0
            if area > max_area:
                max_area = area
        return max_area

Complexities

• Time: (O(n^3)) (all 3-combinations), acceptable for (n \le 50)
• Space: (O(1)) additional space