Largest Triangle Area

easy math geometry enumeration

Problem

Given an array of points in the plane, return the area of the largest triangle that can be formed using any three of them.

Inputpoints = [[0,0],[0,1],[1,0],[0,2],[2,0]]

Output2.0

Triangle (0,0)-(0,2)-(2,0) has area 2.

points

def largestTriangleArea(points):
    n = len(points)
    best = 0.0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                x3, y3 = points[k]
                area = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
                if area > best: best = area
    return best

var largestTriangleArea = function(points) {
    const n = points.length;
    let best = 0;
    for (let i = 0; i < n; i++)
        for (let j = i+1; j < n; j++)
            for (let k = j+1; k < n; k++) {
                const [x1,y1]=points[i], [x2,y2]=points[j], [x3,y3]=points[k];
                const a = 0.5 * Math.abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
                if (a > best) best = a;
            }
    return best;
};

class Solution {
    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                for (int k = j+1; k < n; k++) {
                    int x1=points[i][0], y1=points[i][1];
                    int x2=points[j][0], y2=points[j][1];
                    int x3=points[k][0], y3=points[k][1];
                    double a = 0.5 * Math.abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
                    if (a > best) best = a;
                }
        return best;
    }
}

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double best = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                for (int k = j+1; k < n; k++) {
                    int x1=points[i][0], y1=points[i][1];
                    int x2=points[j][0], y2=points[j][1];
                    int x3=points[k][0], y3=points[k][1];
                    double a = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2));
                    if (a > best) best = a;
                }
        return best;
    }
};

Explanation

Since a triangle needs exactly three points, and the number of points is small, the simplest reliable plan is to just try every group of three points and keep the biggest area we find.

The three nested loops with indices i < j < k make sure we look at each triple exactly once, without repeating the same three points in a different order.

For any three points we get the area straight from a formula called the shoelace (cross-product) formula: 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)). The abs keeps the area positive no matter how the points are arranged, and if the three points sit on a line this naturally gives 0.

Example: with points (0,0), (0,2), (2,0) the formula gives 0.5 * abs(0*(2-0) + 0*(0-0) + 2*(0-2)) = 0.5 * abs(-4) = 2.0.

We compare each computed area against best and update it whenever we find a larger one, so after all triples are checked best holds the answer.

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