Largest Triangle Area solution and explanation
Google
9 more videos on this problem
Largest Triangle Area | Heron | Shoelace | Leetcode 812 | codestorywithMIKcodestorywithMIK · 14:49 · 7K views
812. Largest Triangle Area (Leetcode Easy)Programming Live with Larry · 8:41 · 2K views
Largest Triangle Area | Leetcode 812nETSETOS · 2:18 · 1K views
812. Largest Triangle Area | Leetcode Daily - PythonLeetcode Daily · 4:37 · 1K views
Largest Triangle Area | Leetcode 812 | Hindi Explaination | Leetcode | DSA | Code With DeepakCode with Deepak · 12:03 · 740 views
812. Largest Triangle Area || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 3:39 · 702 views
Largest Triangle Area | LeetCode 812 | Shoelace FormulaSanyam IIT Guwahati · 4:28 · 700 views
Largest Triangle Area | LeetCode 812 | Shoelace formula | Java Code | Developer CoderDeveloper Coder · 9:15 · 298 views
Leetcode solving Python : 812. Largest Triangle AreaMath Geeks · 3:13 · 286 views
Leetcode | 812 Largest Triangle Area | Java | Mathematic ApproachCakot Coding · 14:57 · 113 views
The problem
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.
Approach overview
Problem Overview: You are given a list of 2D points on a plane. The task is to choose any three distinct points that form a triangle with the maximum possible area. If multiple triangles exist, return the largest area among them.
Approach 1: Brute Force Using Determinant Formula (Time: O(n^3), Space: O(1))
The direct method checks every possible combination of three points. Use three nested loops to iterate through triplets (i, j, k). For each triplet, compute the triangle's area using the determinant-based formula: area = |x1(y2−y3) + x2(y3−y1) + x3(y1−y2)| / 2. This formula comes from coordinate geometry and works for any orientation of points. Track the maximum area seen during iteration. Since every combination must be examined, the runtime is O(n^3), but the implementation is straightforward and uses constant extra space.
This approach works well because the constraint sizes are small enough that enumerating all triangles is feasible. The determinant formula avoids computing side lengths or using Heron's formula, keeping the computation simple and numerically stable.
Approach 2: Optimized Formulaic Approach Using Shoelace Formula (Time: O(n^3), Space: O(1))
The Shoelace formula provides a clean way to compute the area of a polygon using coordinates. For a triangle with vertices (x1,y1), (x2,y2), and (x3,y3), the area becomes 0.5 * |x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3|. The algorithm still iterates through all combinations of three points from the array of coordinates, but the calculation step becomes a single expression derived from the Shoelace rule used in computational math.
This formula avoids intermediate steps and expresses the triangle area directly in terms of cross products of coordinates. The runtime remains O(n^3) because the number of point triplets dominates the cost. Space complexity stays O(1) since only a few numeric variables are used while scanning the combinations.
Recommended for interviews: Interviewers typically expect the brute-force combination approach combined with a correct geometric area formula. Enumerating all point triplets demonstrates that you understand the search space, while applying the determinant or Shoelace formula shows familiarity with coordinate geometry. The key is recognizing that triangle area can be computed directly from coordinates without calculating side lengths.
Approach 1: Brute Force Approach using Determinant Formula
This approach considers every combination of three points and calculates the area using the determinant formula for the area of a triangle. Given three points (x1, y1), (x2, y2), (x3, y3), the area A can be computed as:
A = 0.5 * |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|
We iterate over all combinations of three points, calculate the area for each, and keep track of the maximum area encountered.
from typing import List
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
def calculateArea(p1, p2, p3):
return abs((p1[0] * (p2[1] - p3[1]) +
p2[0] * (p3[1] - p1[1]) +
p3[0] * (p1[1] - p2[1])) / 2.0)
max_area = 0
n = len(points)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
max_area = max(max_area, calculateArea(points[i], points[j], points[k]))
return max_area
# Example usage:
solution = Solution()
print(solution.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))import java.util.List;
import java.util.ArrayList;
public class LargestTriangle {
public double largestTriangleArea(int[][] points) {
double maxArea = 0.0;
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
for (int k = j + 1; k < points.length; k++) {
double area = calculateArea(points[i], points[j], points[k]);
maxArea = Math.max(maxArea, area);
}
}
}
return maxArea;
}
private double calculateArea(int[] p1, int[] p2, int[] p3) {
return Math.abs(p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])) / 2.0;
}
public static void main(String[] args) {
LargestTriangle lt = new LargestTriangle();
int[][] points = {{0,0},{0,1},{1,0},{0,2},{2,0}};
System.out.println(lt.largestTriangleArea(points));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
double calculateArea(vector<int>& p1, vector<int>& p2, vector<int>& p3) {
return fabs(p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])) / 2.0;
}
double largestTriangleArea(vector<vector<int>>& points) {
double maxArea = 0.0;
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
for (int k = j + 1; k < points.size(); k++) {
double area = calculateArea(points[i], points[j], points[k]);
maxArea = max(maxArea, area);
}
}
}
return maxArea;
}function largestTriangleArea(points) {
const calculateArea = (p1, p2, p3) => {
return Math.abs(p1[0] * (p2[1] - p3[1]) +
p2[0] * (p3[1] - p1[1]) +
p3[0] * (p1[1] - p2[1])) / 2.0;
};
let maxArea = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
maxArea = Math.max(maxArea, calculateArea(points[i], points[j], points[k]));
}
}
}
return maxArea;
}
// Example usage
console.log(largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
float calculateArea(int *p1, int *p2, int *p3) {
return fabs(p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])) / 2.0;
}
float largestTriangleArea(int** points, int pointsSize, int* pointsColSize) {
float maxArea = 0;
for (int i = 0; i < pointsSize; i++) {
for (int j = i + 1; j < pointsSize; j++) {
for (int k = j + 1; k < pointsSize; k++) {
float area = calculateArea(points[i], points[j], points[k]);
if (area > maxArea) {
maxArea = area;
}
}
}
}
return maxArea;
}using System;
public class Solution {
public double LargestTriangleArea(int[][] points) {
double maxArea = 0.0;
for (int i = 0; i < points.Length; i++) {
for (int j = i + 1; j < points.Length; j++) {
for (int k = j + 1; k < points.Length; k++) {
double area = CalculateArea(points[i], points[j], points[k]);
maxArea = Math.Max(maxArea, area);
}
}
}
return maxArea;
}
private double CalculateArea(int[] p1, int[] p2, int[] p3) {
return Math.Abs(p1[0] * (p2[1] - p3[1]) +
p2[0] * (p3[1] - p1[1]) +
p3[0] * (p1[1] - p2[1])) / 2.0;
}
public static void Main(string[] args) {
var solution = new Solution();
int[][] points = new int[][]{
new int[]{0,0},new int[]{0,1},new int[]{1,0},new int[]{0,2},new int[]{2,0}
};
Console.WriteLine(solution.LargestTriangleArea(points));
}
}The Python solution defines an inner function calculateArea to abstract the area computation. The main function utilizes three nested loops to find the maximum triangle area.
Time Complexity: O(n^3) because each triplet of points is tested.
Space Complexity: O(1) as no additional memory outside of loop counters is used.
Approach 2: Optimized Formulaic ApproachUsing Shoelace Formula
This approach also solves the problem using the Shoelace formula (an efficacious method for calculating the area of a polygon). While typically useful for polygons, here we can apply it to triangles. Given three points (x1, y1), (x2, y2), and (x3, y3), the triangle area A is:
A = 0.5 * |x1y2 + x2y3 + x3y1 - y1x2 - y2x3 - y3x1|
While this is similar to the determinant approach, it clarifies computational steps explicitly and can be implemented directly.
from typing import List
class Solution:
def largestTriangleArea(self, points: List[List[int]]) -> float:
def calculateArea(p1, p2, p3):
return abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])) / 2.0
max_area = 0
n = len(points)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
max_area = max(max_area, calculateArea(points[i], points[j], points[k]))
return max_area
# Example usage:
solution = Solution()
print(solution.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))import java.util.List;
import java.util.ArrayList;
public class LargestTriangle {
public double largestTriangleArea(int[][] points) {
double maxArea = 0.0;
for (int i = 0; i < points.length; i++) {
for (int j = i + 1; j < points.length; j++) {
for (int k = j + 1; k < points.length; k++) {
double area = calculateArea(points[i], points[j], points[k]);
maxArea = Math.max(maxArea, area);
}
}
}
return maxArea;
}
private double calculateArea(int[] p1, int[] p2, int[] p3) {
return Math.abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])) / 2.0;
}
public static void main(String[] args) {
LargestTriangle lt = new LargestTriangle();
int[][] points = {{0,0},{0,1},{1,0},{0,2},{2,0}};
System.out.println(lt.largestTriangleArea(points));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
double calculateArea(vector<int>& p1, vector<int>& p2, vector<int>& p3) {
return fabs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])) / 2.0;
}
double largestTriangleArea(vector<vector<int>>& points) {
double maxArea = 0.0;
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
for (int k = j + 1; k < points.size(); k++) {
double area = calculateArea(points[i], points[j], points[k]);
maxArea = max(maxArea, area);
}
}
}
return maxArea;
}function largestTriangleArea(points) {
const calculateArea = (p1, p2, p3) => {
return Math.abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])) / 2.0;
};
let maxArea = 0;
const n = points.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
maxArea = Math.max(maxArea, calculateArea(points[i], points[j], points[k]));
}
}
}
return maxArea;
}
// Example usage
console.log(largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
float calculateArea(int *p1, int *p2, int *p3) {
return fabs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - p1[1] * p2[0] - p2[1] * p3[0] - p3[1] * p1[0]) / 2.0;
}
float largestTriangleArea(int** points, int pointsSize, int* pointsColSize) {
float maxArea = 0;
for (int i = 0; i < pointsSize; i++) {
for (int j = i + 1; j < pointsSize; j++) {
for (int k = j + 1; k < pointsSize; k++) {
float area = calculateArea(points[i], points[j], points[k]);
maxArea = fmax(maxArea, area);
}
}
}
return maxArea;
}using System;
public class Solution {
public double LargestTriangleArea(int[][] points) {
double maxArea = 0.0;
for (int i = 0; i < points.Length; i++) {
for (int j = i + 1; j < points.Length; j++) {
for (int k = j + 1; k < points.Length; k++) {
double area = CalculateArea(points[i], points[j], points[k]);
maxArea = Math.Max(maxArea, area);
}
}
}
return maxArea;
}
private double CalculateArea(int[] p1, int[] p2, int[] p3) {
return Math.Abs(p1[0] * p2[1] + p2[0] * p3[1] + p3[0] * p1[1] - (p1[1] * p2[0] + p2[1] * p3[0] + p3[1] * p1[0])) / 2.0;
}
public static void Main(string[] args) {
var solution = new Solution();
int[][] points = new int[][]{
new int[]{0,0},new int[]{0,1},new int[]{1,0},new int[]{0,2},new int[]{2,0}
};
Console.WriteLine(solution.LargestTriangleArea(points));
}
}This Python implementation uses the Shoelace formula through a helper function to calculate areas of triangles formed by the points. We iterate over possible point combinations to determine the largest area.
Time Complexity: O(n^3) since all triplets of points are considered.
Space Complexity: O(1) as we only use internal iteration variables.
Approach 3: Default Approach
Given three points (x_1, y_1), (x_2, y_2), (x_3, y_3) on a plane, the area formula is:
$S = \frac{1}{2} \left| x_1y_2 + x_2y_3 + x_3y_1 - x_1y_3 - x_2y_1 - x_3y_2 \right|
We can enumerate all combinations of three points and calculate the maximum area.
The time complexity is O(n^3), where n is the number of points. The space complexity is O(1)$.
function largestTriangleArea(points: number[][]): number {
let ans = 0;
for (const [x1, y1] of points) {
for (const [x2, y2] of points) {
for (const [x3, y3] of points) {
const u1 = x2 - x1,
v1 = y2 - y1;
const u2 = x3 - x1,
v2 = y3 - y1;
const t = Math.abs(u1 * v2 - u2 * v1) / 2;
ans = Math.max(ans, t);
}
}
}
return ans;
}func largestTriangleArea(points [][]int) float64 {
ans := 0.0
for _, p1 := range points {
x1, y1 := p1[0], p1[1]
for _, p2 := range points {
x2, y2 := p2[0], p2[1]
for _, p3 := range points {
x3, y3 := p3[0], p3[1]
u1, v1 := x2-x1, y2-y1
u2, v2 := x3-x1, y3-y1
t := float64(abs(u1*v2-u2*v1)) / 2.0
ans = math.Max(ans, t)
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn largest_triangle_area(points: Vec<Vec<i32>>) -> f64 {
let mut ans: f64 = 0.0;
for point1 in &points {
let (x1, y1) = (point1[0], point1[1]);
for point2 in &points {
let (x2, y2) = (point2[0], point2[1]);
for point3 in &points {
let (x3, y3) = (point3[0], point3[1]);
let u1 = x2 - x1;
let v1 = y2 - y1;
let u2 = x3 - x1;
let v2 = y3 - y1;
let t = ((u1 * v2 - u2 * v1) as f64).abs() / 2.0;
ans = ans.max(t);
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach using Determinant Formula | Time Complexity: O(n^3) because each triplet of points is tested. |
| Optimized Formulaic ApproachUsing Shoelace Formula | Time Complexity: O(n^3) since all triplets of points are considered. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Using Determinant Formula | O(n^3) | O(1) | Simple implementation when constraints allow checking all point triplets |
| Shoelace Formula Iteration | O(n^3) | O(1) | Cleaner coordinate-based area calculation in geometry-heavy problems |
Frequently asked questions
Is Largest Triangle Area easy or hard?
Largest Triangle Area is classified as an Easy problem on LeetCode. The main challenge is recalling the triangle area formula using coordinates and applying it while iterating through all point combinations.
Largest Triangle Area Python/Java solution
Implement three nested loops to generate all point triplets and compute the triangle area using the Shoelace or determinant formula. Track the maximum area encountered. This approach works identically in Python, Java, C++, and other languages with O(n^3) time complexity.
How to solve Largest Triangle Area in O(n)?
An O(n) solution is not feasible for the general problem because any triangle requires choosing three points. The algorithm must evaluate combinations of points, which leads to O(n^3) in the straightforward solution. Geometry formulas only optimize the area computation, not the number of combinations.
What is the best approach for Largest Triangle Area?
The standard approach is brute force enumeration of all point triplets combined with the determinant or Shoelace formula to compute triangle area. This checks every combination of three points and tracks the maximum area. Time complexity is O(n^3) with O(1) extra space.
Is Largest Triangle Area asked at Google/Amazon/Meta?
Geometry and coordinate math problems like Largest Triangle Area occasionally appear in coding interviews at companies such as Amazon and Google, especially when testing mathematical reasoning with arrays of points. The focus is usually on recognizing the triangle area formula from coordinates.
What data structure is used in Largest Triangle Area?
The problem primarily uses arrays to store the list of 2D points. The algorithm iterates through combinations of these points and applies a geometry formula to compute the area. No advanced data structures are required.
What is the time complexity of Largest Triangle Area?
The time complexity is O(n^3) because every combination of three points from the input must be evaluated. For each triplet, the triangle area is computed using a constant-time geometry formula. Space complexity remains O(1).