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
Difficulty
and has an acceptance rate of about 62% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Geometry
- Math
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 976: Largest Perimeter Triangle
Solved On The Same Day
- problem 824: Goat Latin
- problem 844: Backspace String Compare
- problem 791: Custom Sort String
- problem 794: Valid Tic-Tac-Toe State
- problem 807: Max Increase to Keep City Skyline
- problem 813: Largest Sum of Averages
- problem 814: Binary Tree Pruning
- problem 825: Friends Of Appropriate Ages
- problem 848: Shifting Letters
- problem 849: Maximize Distance to Closest Person
- problem 815: Bus Routes
Extra
- 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