algoadvance

Leetcode 812. Largest Triangle Area

Problem Statement

Given a list of points on the 2D plane, you should compute the area of the largest triangle that can be formed by any 3 of the provided points.

You are given an array of points points where points[i] = [xi, yi] come in pairs representing the coordinates of points on a 2D plane.

Return the area of the largest triangle that can be formed.

Clarifying Questions

1. Constraints:
   • How many points are given? (1 <= points.length <= 50)
   • What is the range of the coordinates? (-50 <= xi, yi <= 50)
2. Output:
   • Should the area be given as a floating point number with a certain precision?
3. Unique Points:
   • Can points be repeated in the input? (Assume all points are unique for simplicity.)

Strategy

• The area of a triangle given coordinates of its vertices ((x1, y1)), ((x2, y2)), and ((x3, y3)) can be computed using the determinant formula: [ \text{Area} = \frac{1}{2} \left| x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2) \right| ]
• Iterate through all combinations of 3 points and calculate the area using the formula above.
• Keep track of and return the largest area found.

Code

#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double maxArea = 0.0;
        
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    double area = 0.5 * fabs(points[i][0] * (points[j][1] - points[k][1]) +
                                             points[j][0] * (points[k][1] - points[i][1]) +
                                             points[k][0] * (points[i][1] - points[j][1]));
                    maxArea = max(maxArea, area);
                }
            }
        }
        
        return maxArea;
    }
};

Time Complexity

• Combinatorial Enumeration: The algorithm checks all combinations of three points from the list. The number of combinations is given by ( \binom{n}{3} ) which is ( \frac{n(n-1)(n-2)}{6} ).
• The time complexity is ( O(n^3) ), which is feasible given the constraints ( n \leq 50 ).

This solution iterates through each combination of three points, calculates the triangle area for each combination, and keeps track of the maximum area encountered. Given the constraints, this approach should perform well.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?