Skip to content

← leetcode

Largest Triangle Area

· Easy

LeetCode problem 812

Simply, run a triple for loop through points. For any three points, P_i, P_j & P_k, the area of the triangle is simply just half the cross-product of P_j - P_i & P_k - P_i, giving us the formula:

area=(xj−xi)(yk−yi)−(xk−xi)(yj−yi)2\begin{equation*} \text{area} = \frac{(x_j - x_i)(y_k - y_i) - (x_k - x_i)(y_j - y_i)}{2} \end{equation*}

code

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        double ans = 0;
        for (int i = 0; i < points.size()-2; ++i) {
            for (int j = i+1; j < points.size()-1; ++j) {
                for (int k = j+1; k < points.size(); ++k) {
                    double area = (double) abs((points[k][1] - points[i][1]) * (points[j][0] - points[i][0]) - (points[j][1] - points[i][1]) * (points[k][0] - points[i][0]))/2;
                    ans = max(ans, area);
                }
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n^3) where n denotes the number of elements inside points
  • Space: O(1)

time taken

  • i forgot to time-