830. Largest Triangle Area¶

LeetCode Problem View on GitHub

830. Largest Triangle Area

Easy

Given an array of points on the X-Y plane points where points[i] = [xi, yi], return the area of the largest triangle that can be formed by any three different points. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.

Example 2:

Input: points = [[1,0],[0,0],[0,1]]
Output: 0.50000

Constraints:

• 3 <= points.length <= 50
• -50 <= xi, yi <= 50
• All the given points are unique.

Solution¶

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

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here