Skip to content

830. Largest Triangle Area

Array Math Geometry

Problem - Largest Triangle Area

Easy

Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.

Example 2:

Input: points = [[1,0],[0,0],[0,1]]
Output: 0.50000

 

Constraints:

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • All the given points are unique.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        result = 0
        for x1, y1, in points:
            for x2, y2 in points:
                for x3, y3 in points:
                    u1, v1 = x2 - x1, y2 - y1
                    u2, v2 = x3 - x1, y3 - y1
                    tri = abs(u1 * v2 - u2 * v1) / 2
                    result = max(result, tri)

        return result

Submission Stats:

  • Runtime: 249 ms (5.41%)
  • Memory: 17.8 MB (73.42%)