Largest Perimeter Triangle: Greedy Sorting for the Triangle Inequality
Given an array of positive integers representing possible side lengths, can you pick three that form a triangle, and among all valid triangles, find the one with the largest perimeter? This is LeetCode 976: Largest Perimeter Triangle, an easy problem that introduces the greedy sorting pattern for geometric constraints.
The problem
You are given an integer array nums where each element is a positive integer. Return the largest perimeter of a triangle with a non-zero area that can be formed from three of these lengths. If no valid triangle exists, return 0.
A triangle is valid when the sum of any two sides is strictly greater than the third side. Since the array is not necessarily sorted, you need to figure out which three values to pick and how to verify the triangle inequality efficiently.
Sort descending, check consecutive triples
The brute force approach would check every combination of three elements, giving O(n^3) time. But you can do much better by sorting.
After sorting the array in descending order, the largest values come first. For any index i, the triple (nums[i], nums[i+1], nums[i+2]) is the best candidate starting from that position. Why? Because nums[i] is the largest of the three, and you only need to verify one inequality: nums[i] < nums[i+1] + nums[i+2]. The other two inequalities are automatically satisfied since nums[i] is the biggest side.
If the first triple satisfies the inequality, you are done. That triple gives the largest possible perimeter because any other valid triple would use smaller values. If it fails, move to the next triple (nums[i+1], nums[i+2], nums[i+3]) and check again.
After sorting descending, the first consecutive triple that satisfies nums[i] < nums[i+1] + nums[i+2] gives the answer. You only need to check one inequality per triple because the largest side is always nums[i].
Step-by-step walkthrough
Step 1: Start with the input array
nums = [3, 2, 3, 4]. We need the three sides that form the triangle with the largest perimeter.
Step 2: Sort in descending order
After sorting: [4, 3, 3, 2]. The largest sides come first, so the first valid triple gives the maximum perimeter.
Step 3: Check triple (4, 3, 3)
Is 4 < 3 + 3? That is 4 < 6. Yes! This triple forms a valid triangle. Perimeter = 4 + 3 + 3 = 10.
Step 4: Return the perimeter
The first valid triple gives the largest possible perimeter. Return 4 + 3 + 3 = 10. No need to check further triples.
The code
def largestPerimeter(nums):
nums.sort(reverse=True)
for i in range(len(nums) - 2):
if nums[i] < nums[i + 1] + nums[i + 2]:
return nums[i] + nums[i + 1] + nums[i + 2]
return 0
The solution sorts the array in descending order, then iterates through consecutive triples. For each triple, it checks the one inequality that matters: whether the largest side is strictly less than the sum of the other two. The moment a valid triple is found, it returns the perimeter. If no valid triple exists after scanning the entire array, it returns 0.
The key insight is that you never need to look beyond consecutive elements. If nums[i] is too large for nums[i+1] and nums[i+2], pairing nums[i] with even smaller elements will not help. And any triple using elements smaller than nums[i] will have a smaller perimeter, so the first valid consecutive triple is always optimal.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n^3) | O(1) |
| Sort + greedy | O(n log n) | O(1) |
Sorting dominates at O(n log n). The subsequent linear scan is O(n), which does not change the overall complexity. Space is O(1) if you sort in place (ignoring the space used by the sorting algorithm itself).
The building blocks
Sorting for greedy elimination
Sorting transforms a search problem into a scan problem. Instead of checking all O(n^3) triples, you sort once and walk through consecutive triples in O(n). This same pattern appears in problems like Two Sum (sorted variant), 3Sum, and meeting room scheduling. Whenever you need the "best" combination of elements, sorting often lets you prune the search space dramatically.
The triangle inequality
For three sides a, b, c where a >= b >= c, the triangle inequality reduces to a single check: a < b + c. The other two inequalities (b < a + c and c < a + b) are automatically true because a is the largest. Recognizing when a multi-condition check collapses to a single condition is a useful skill that saves both code and mental overhead.
Edge cases
- Fewer than three elements. The problem guarantees
nums.length >= 3, but if you want to be safe, return0whenlen(nums)<3. - All elements identical. For example,
[5, 5, 5]. The check5<5 + 5is true, so the perimeter is15. - No valid triangle. For example,
[1, 2, 3]. After sorting descending:[3, 2, 1]. Check:3<2 + 1is3<3, which is false. Return0. - Degenerate triangle. Sides
[1, 1, 2]give2<1 + 1which is2<2, false. This correctly excludes zero-area triangles. - Large array with valid triple near the end. The scan may go through many failing triples before finding one. The linear scan ensures you still find it in O(n).
From understanding to recall
The algorithm is clean: sort descending, scan consecutive triples, return the first valid perimeter. But under interview pressure, you might second-guess yourself. Do you check all three inequalities, or just one? Do you scan from the beginning or the end? Do you need to handle ties?
Practicing this problem from scratch a few times locks in the details. You remember that sorting descending means the largest side is always first in the triple, so one inequality check is enough. You remember that consecutive triples are optimal because skipping elements only makes the perimeter smaller. These small details are what separate a confident solution from a shaky one.
Related posts
- Valid Triangle Number - Count valid triangles using the same inequality check
- Sort Array By Parity - Another sort-based greedy approach
- Assign Cookies - Greedy + sorting pattern for optimization