LC-0812 Easy LeetCode

812. Largest Triangle Area

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 62% Topics: Array, Math, Geometry

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(n^3)
# Space: O(1)


class Solution(object):
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        result = 0
        for i in xrange(len(points)-2):
            for j in xrange(i+1, len(points)-1):
                for k in xrange(j+1, len(points)):
                    result = max(result,
                                 0.5 * abs(points[i][0] * points[j][1] +
                                           points[j][0] * points[k][1] +
                                           points[k][0] * points[i][1] -
                                           points[j][0] * points[i][1] -
                                           points[k][0] * points[j][1] -
                                           points[i][0] * points[k][1]))
        return result

Solution from kamyu104/LeetCode-Solutions · MIT