Problem statement

https://leetcode.com/problems/largest-triangle-area/

Solution 1

One way to solve this problem is just check all possible triplets of points.

Complexity

It is O(n^3) for time and O(1) for space.

Code

class Solution:
    def largestTriangleArea(self, points):
        def area(x1, y1, x2, y2, x3, y3):
            return abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
        
        ans = 0
        for [x1, y1], [x2, y2], [x3, y3] in combinations(points, 3):
            ans = max(ans, area(x1, y1, x2, y2, x3, y3))
        return ans/2

Solution 2

There is also O(n^2) solution, using convex hull: we need O(n log n) time to construct convex hull, using for example Graham Scan and then for each node on convex hull we can find triangle with biggest area in O(n), so overall complexity of second step is O(n^2). See https://arxiv.org/pdf/1705.11035.pdf, page 8 for details.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def largestTriangleArea(self, points):
        def cross(p1, p2, p3):
            return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])
        
        def ConvexHull(points):
            start = min(points)
            points.pop(points.index(start))

            points.sort(key=lambda p: (atan2(p[1]-start[1],p[0]-start[0]),-p[1], p[0]))

            ans = [start]
            for p in points:
                ans.append(p)
                while len(ans) > 2 and cross(ans[-3], ans[-2], ans[-1]) < 0:
                    ans.pop(-2)
            return ans

        def rootTriangle(a):
            ans, c = 0, (a + 2) % n
            for b in range(a+1, a+n):
                while abs(cross(H[a], H[b%n], H[(c+1)%n])) >= abs(cross(H[a], H[b%n], H[c])):
                    c = (c + 1) % n
                ans = max(ans, abs(cross(H[a], H[b%n], H[c%n])))
            return ans
        
        H = ConvexHull(points)
        n = len(H)
        return max(rootTriangle(a) for a in range(n))/2

Remark

There is also O(n log n) time complexity solution, using the same article, which is quite difficult to implement, but which is quite interesting to investigate, the idea is divide and conquer.