Problem 812

Abstract / Summary

Given a set of points in the plane, find the maximum area of a triangle formed by any three points.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0812.py

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        result = 0
        for x1, y1 in points:
            for x2, y2 in points:
                for x3, y3 in points:
                    area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
                    result = max(result, area)
        return result
9 lines | 371 bytes | submitted October 9, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 62% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Geometry
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a method largestTriangleArea that receives a list of 2-D points and returns the maximum area of any triangle that can be formed from three of those points. The algorithm enumerates every possible triple of points, computes the signed area using the shoelace formula, takes its absolute value, and keeps the greatest value encountered.

Core Logic

The method begins by initializing a variable to hold the best area found so far.

result = 0

It then proceeds with three nested loops, each iterating over the entire collection of points. The outermost loop extracts the coordinates of the first vertex, the middle loop extracts the second vertex, and the innermost loop extracts the third vertex.

for x1, y1 in points:
    for x2, y2 in points:
        for x3, y3 in points:

Inside the innermost loop the area of the triangle formed by the current triple is calculated. The expression implements the shoelace formula, which yields twice the signed area; multiplying by 0.5 and applying abs converts it to the actual geometric area.

area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))

After the area is obtained, the algorithm updates the running maximum using Python’s built-in max function.

result = max(result, area)

When all triples have been examined, the method returns the stored maximum.

return result

Edge Cases Handled

When the input list is empty, the three nested loops never execute, leaving result at its initial value of 0. Consequently the method returns 0, which correctly represents the fact that no triangle can be formed.

If the list contains fewer than three distinct points, the loops still run but every computed area will be zero because the three selected points are either identical or collinear. The abs operation ensures that a zero area is recorded, and the final return value remains 0.

The algorithm also gracefully handles duplicate points within the list. Selecting the same point more than once yields a degenerate triangle with zero area, which does not affect the maximum because any non-degenerate triangle will produce a positive area that supersedes the zero values.

Collinear points are another special situation. For any three points lying on a straight line the shoelace expression evaluates to zero, and the absolute value preserves that result. The method therefore correctly ignores such triples when searching for the largest area.

Performance Optimizations Observed

The implementation relies on plain arithmetic operations without invoking any heavy library functions, which keeps the per-iteration cost low. By using the direct form of the shoelace formula, the code avoids unnecessary intermediate structures or function calls.

The use of the built-in max function to update the best area is efficient because it delegates the comparison to a highly optimized native routine.

Storing the intermediate area in a local variable (area) before the comparison reduces repeated evaluation of the arithmetic expression, ensuring that each triple’s area is computed exactly once.

Overall, the design emphasizes straightforward computation and leverages Python’s native constructs to maintain a tight inner loop.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big bag of colorful stickers scattered on a table. Each sticker is at a specific spot. This code is like a curious little explorer trying to find the biggest triangle that can fit by connecting any three of those stickers.

First, the code picks one sticker to be the bottom corner of a triangle. Then, it picks a second sticker to be another corner, and finally, it picks a third sticker to be the top point.

Once it has three corners, the code does a bit of magic math to measure how much space is inside that triangle. After it measures that triangle, it remembers how big it is. If it finds another triangle later that is even bigger, it forgets the old one and keeps the new, larger one in its memory instead.

It does this over and over again, peeking at every possible combination of three stickers on the table. By the time it finishes looking at every group, it has found the very biggest triangle possible from all the stickers. It is just like searching through a toy box to find the largest shape you can make.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.67 | σ = 1.91

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Rust Python Go TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
withaarzoo C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
ruoru Rust
suxrobGM C#
varunu28 Java
withaarzoo C++
zfang399 C++
35 links | 21 authors | 10 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

2 easy 8 medium 1 hard
12 solutions   October 9, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality