Skip to main content
Talentd

Largest Triangle Area - Solution & Explanation

EasyArrayMathGeometry19 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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.

We define a helper function calculateArea that takes three points and computes the area of the triangle formed by these points using the determinant formula. The main function iterates through all combinations of three points and calculates the area, updating the maximum if a larger area is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the number of points as we check every combination of three points.
Space Complexity: O(1), as we are only using a constant amount of extra space.

Try this approach in the editor →

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.

The C version uses the Shoelace theorem by simply formalizing it in a helper function calculateArea. It considers all triplets and records the largest valid area, returning it.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3); still involves three nested loops.
Space Complexity: O(1); no extra space beyond simple counters.

Try this approach in the editor →

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)$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach using Determinant Formula

Time Complexity: O(n^3), where n is the number of points as we check every combination of three points.
Space Complexity: O(1), as we are only using a constant amount of extra space.

Optimized Formulaic ApproachUsing Shoelace Formula

Time Complexity: O(n^3); still involves three nested loops.
Space Complexity: O(1); no extra space beyond simple counters.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Using Determinant FormulaO(n^3)O(1)Simple implementation when constraints allow checking all point triplets
Shoelace Formula IterationO(n^3)O(1)Cleaner coordinate-based area calculation in geometry-heavy problems

Video Solution

Largest Triangle Area | Heron | Shoelace | Leetcode 812 | codestorywithMIK • codestorywithMIK • 7,122 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Largest Triangle Area with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Perimeter Triangle