LeetCode Solutions Blog

Largest Triangle Area

Number: 830

Difficulty: Easy

Paid? No

Problem Description

Given an array of unique points on the X-Y plane, determine the area of the largest triangle that can be formed by any three different points. The answer is accepted if it is within 10^-5 of the actual area.

Key Insights

Compute the area of a triangle using the formula: Area = |(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))| / 2.
Use a brute force approach to check all possible combinations of three points.
The constraints (3 <= points.length <= 50) allow an O(n^3) solution with triple nested loops.

Space and Time Complexity

Time Complexity: O(n^3) since we iterate over all triplets of points.
Space Complexity: O(1) as only a few extra variables are used.

Solution

The solution involves iterating through every possible combination of three distinct points from the given list. For each triplet, compute the area using the determinant formula, update the maximum area found, and finally, return this maximum area. The use of simple arithmetic operations ensures that the algorithm runs efficiently even for the maximum constraint.

Code Solutions

# Function to compute the area of a triangle formed by three points
def triangle_area(p1, p2, p3):
    # Using the determinant formula to get the area
    return abs(p1[0] * (p2[1] - p3[1]) +
               p2[0] * (p3[1] - p1[1]) +
               p3[0] * (p1[1] - p2[1])) / 2.0

def largest_triangle_area(points):
    max_area = 0.0  # Variable to keep track of the maximum area found
    n = len(points)  # Total number of points
    # Iterate over all triplets of points
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                area = triangle_area(points[i], points[j], points[k])
                # Update max_area if the current triangle has a larger area
                if area > max_area:
                    max_area = area
    return max_area

# Example test
points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
print(largest_triangle_area(points))  # Expected output: 2.00000