Domain 1EasyCORE

Largest Triangle Area

The problem requires finding the largest possible area of a triangle that can be formed by any three points from a given list of points in the plane. The input is a list of points where each point is represented as a pair of coordinates [x, y]. The output should be the area of the largest triangle.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

812. Largest Triangle Area

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 59.1%


Problem Breakdown

The problem requires finding the largest possible area of a triangle that can be formed by any three points from a given list of points in the plane. The input is a list of points where each point is represented as a pair of coordinates [x, y]. The output should be the area of the largest triangle.

Inputs:

  • A list of points points where each point is [x, y].

Outputs:

  • A single float representing the area of the largest triangle that can be formed by any three points from the input list.

Implicit Constraints or Tricky Edge Cases:

  • The number of points is between 3 and 50.
  • No two points are duplicated.
  • Coordinates range from -50 to 50.
  • The answer should be accurate within 10^-6 of the true value.

Intuition

To solve this problem, we need to calculate the area of all possible triangles formed by any three points and then find the maximum area. A brute-force approach would involve checking every combination of three points, which is feasible given the constraints (3 <= points.length <= 50). However, a more efficient approach can be derived using the Shoelace formula (or Gauss’s area formula) for calculating the area of a triangle given its vertices.

The Shoelace formula states that for a triangle with vertices ((x_1, y_1)), ((x_2, y_2)), and ((x_3, y_3)), the area (A) is given by: [ A = \frac{1}{2} \left| x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2) \right| ]

This formula allows us to compute the area in constant time for each set of three points, making it efficient enough for our input size.

Approach

  1. Initialize a variable max_area to store the maximum area found.
  2. Iterate through all combinations of three points from the list using nested loops.
  3. For each combination of three points ((x_1, y_1)), ((x_2, y_2)), and ((x_3, y_3)):
    • Calculate the area using the Shoelace formula.
    • Update max_area if the calculated area is larger than the current max_area.
  4. Return the value of max_area.

Complexity Analysis

  • Time Complexity: (O(n^3)), where (n) is the number of points. This is because we are checking every combination of three points.
  • Space Complexity: (O(1)), as we only use a fixed amount of extra space for storing variables.

Solution

def largestTriangleArea(points):
    max_area = 0
    n = len(points)
    
    # Iterate through all combinations of three points
    for i in range(n - 2):
        x1, y1 = points[i]
        for j in range(i + 1, n - 1):
            x2, y2 = points[j]
            for k in range(j + 1, n):
                x3, y3 = points[k]
                
                # Calculate the area using the Shoelace formula
                area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0
                
                # Update max_area if the current area is larger
                if area > max_area:
                    max_area = area
    
    return max_area

Edge Cases Handled

  • Minimum number of points: The function assumes that there are at least three points, as specified in the problem constraints.
  • Maximum number of points: The function can handle up to 50 points efficiently within the given time and space constraints.
  • Negative coordinates: The Shoelace formula works correctly with negative coordinates.
  • Zero area triangles: If any set of three points is collinear, the calculated area will be zero, which is handled naturally by the algorithm.