Abstract / Summary

Given a list of side lengths, find the largest perimeter that can form a triangle.

Note

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

This problem is ranked as

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

Typical patterns to solve this problem:

• Array
• Greedy
• Math
• Sorting

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.

Overview

The largestPerimeter method receives a mutable reference to a vector of integers that represent side lengths. Its goal is to find the greatest possible perimeter of a non-degenerate triangle that can be formed from any three distinct elements of the input. If no such triangle exists, the method returns 0. The implementation follows a three-level nested iteration after arranging the data in descending order, and it incorporates several early-exit checks that prune the search space.

Key Steps

Sorting and arranging in descending order

The first two statements prepare the data for efficient scanning.

sort(nums.begin(), nums.end());
reverse(nums.begin(), nums.end());

sort orders the elements in non-decreasing order, and reverse flips the sequence so that the largest values appear first. This ordering enables the algorithm to consider the biggest possible sides early and to apply monotonic break conditions safely.

Selecting the longest side (outer loop)

The outermost loop iterates over each candidate for the longest side a.

for (int x = 0; x < nums.size(); x++)
{
    int a = nums[x];
    if (3*a <= maxx)
        break;
    …
}

The loop variable x indexes the vector, and a stores the current side length. The guard if (3*a <= maxx) break; stops further exploration once three copies of the current a could not improve the best perimeter already found (maxx). Because the array is descending, any later a will be smaller, making the condition sufficient to terminate the outer loop early.

Choosing the middle side (middle loop)

For each a, the algorithm picks a second side b that is strictly smaller in index.

for (int y = x+1; y < nums.size(); y++)
{
    int b = nums[y];
    if (a + b + b <= maxx)
        break;
    …
}

Here b is the next candidate side. The test if (a + b + b <= maxx) break; leverages the fact that the third side c cannot exceed b (due to descending order). If even the sum of a and two copies of b fails to beat maxx, no further b values (which are smaller) can succeed, so the middle loop exits early.

Picking the smallest side (inner loop)

The innermost loop examines each possible third side c.

for (int z = y+1; z < nums.size(); z++)
{
    int c = nums[z];

    if (b + c <= a)
        break;
    if (a + b + c <= maxx)
        break;

    maxx = a + b + c;
}

The first condition if (b + c <= a) break; enforces the triangle inequality: for a valid triangle the sum of the two shorter sides must exceed the longest side. Because c only gets smaller as z increases, once this inequality fails it will never hold again, allowing an immediate exit from the inner loop. The second condition if (a + b + c <= maxx) break; stops the search when the current perimeter cannot improve the best result. When both checks pass, the perimeter a + b + c is larger than any previously recorded value, and maxx is updated accordingly.

Returning the result

After all feasible triples have been examined (or pruned), the method returns the maximum perimeter found.

return maxx;

If no triple satisfied the triangle inequality, maxx remains at its initial value 0, which the caller interprets as “no triangle possible”.

Edge Cases Handled

The algorithm gracefully handles inputs that contain fewer than three elements because the outer loop’s range is bounded by nums.size(). When the size is less than three, the inner loops never execute, leaving maxx at 0.

When the vector consists entirely of values that cannot satisfy the triangle inequality (for example, a monotonic decreasing sequence where each element is at least the sum of the two following ones), the inner break if (b + c <= a) break; triggers immediately, preventing unnecessary iterations.

If the vector contains many duplicate large values, the early-exit condition if (3*a <= maxx) break; ensures that once a maximal perimeter has been discovered, any further exploration of equal or smaller a values stops, even when duplicates could otherwise cause redundant checks.

Performance Optimizations

The most noticeable optimization is the descending ordering of the input, which makes the three nested loops amenable to monotonic break statements. By guaranteeing that each subsequent candidate side is not larger than the previous, the algorithm can safely conclude that once a condition fails for a given index, it will continue to fail for all larger indices.

The outermost early-exit if (3*a <= maxx) break; eliminates entire sections of the search space once the current largest side is too small to improve the best perimeter.

Similarly, the middle loop’s guard if (a + b + b <= maxx) break; leverages the fact that the third side cannot exceed b, allowing the loop to stop without scanning the remaining elements.

Inside the innermost loop, the triangle-inequality check if (b + c <= a) break; provides a decisive cut-off: as soon as the sum of the two shorter sides falls short of the longest side, no further c values can satisfy the inequality, so the loop terminates instantly.

Finally, the second inner condition if (a + b + c <= maxx) break; prevents the algorithm from updating maxx with a non-improving perimeter and avoids needless continuation of the innermost loop once the current combination cannot beat the best known result.

Collectively, these early-exit strategies reduce the effective number of examined triples dramatically, especially for large inputs with many elements that cannot form a triangle, yielding a runtime that is far better than the naïve cubic enumeration.

Imagine you have a big bucket full of wooden sticks of all different lengths, and you want to build a triangle using three of them. To make sure the sticks fit together just right, there is a special rule where the two shorter sticks must add up to be longer than the longest stick.

The computer starts by putting all the sticks in a line from the longest to the shortest so that it is easier to find the big ones first. It looks at three sticks at a time to see if they can form a triangle. It checks the rule by adding the lengths of the two smaller sticks together and comparing them to the longest one.

If it finds a good set of sticks that makes a triangle, it measures how long the outside edge of that triangle is by adding all three sides together. Then, it remembers that measurement. As it keeps looking at other combinations of sticks, it always checks if a new triangle is bigger than the one it found before. If it finds a bigger one, it keeps the new measurement instead. After it goes through all the different sticks, it knows which triangle had the longest edge of them all.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

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

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	Python				Go	C	Rust	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim								C
	everthis				JS
	fartem						Ruby
	FelixFan1122		Java
	fpdjsns	C++
	fsq	C++
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	pruthvikp			Python
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, 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
FelixFan1122	Java
fpdjsns	C++
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
pruthvikp	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
withaarzoo	C++

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