Largest Perimeter Triangle - Solution & Explanation
Problem Statement
Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.
Example 1:
Input: nums = [2,1,2] Output: 5 Explanation: You can form a triangle with three side lengths: 1, 2, and 2.
Example 2:
Input: nums = [1,2,1,10] Output: 0 Explanation: You cannot use the side lengths 1, 1, and 2 to form a triangle. You cannot use the side lengths 1, 1, and 10 to form a triangle. You cannot use the side lengths 1, 2, and 10 to form a triangle. As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.
Constraints:
3 <= nums.length <= 1041 <= nums[i] <= 106
Approach Overview
Problem Overview: You get an array of positive integers where each value represents a possible triangle side length. Your goal is to choose three numbers that form a valid triangle and return the largest possible perimeter. A triangle is valid only if the triangle inequality holds: a + b > c for sides a ≤ b ≤ c.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
The straightforward solution tries every combination of three numbers. Use three nested loops to pick indices i, j, and k, then check whether the selected sides satisfy the triangle inequality. If they do, compute the perimeter and keep track of the maximum. This method directly models the definition of a triangle and guarantees correctness. However, the time complexity grows quickly because there are O(n³) triplets to evaluate. It works only for small arrays and mainly serves as a conceptual baseline before optimizing.
Approach 2: Greedy Approach with Sorting (O(n log n) time, O(1) space)
A key observation simplifies the search: if the array is sorted, you only need to check consecutive triples from the largest values downward. Sort the array using a standard algorithm from the sorting category. After sorting in non‑decreasing order, iterate from the end and test triplets (nums[i-2], nums[i-1], nums[i]). If nums[i-2] + nums[i-1] > nums[i], those three sides form a valid triangle and also produce the maximum perimeter because you started with the largest sides.
This works due to the triangle inequality: when the array is sorted, nums[i] is the largest side. If the two sides immediately before it cannot satisfy a + b > c, any smaller pair will also fail. That means you can safely move left and continue checking. The algorithm performs one sort followed by a single linear scan, making it efficient for large inputs. The idea combines array traversal with a simple greedy choice: pick the largest possible sides first and stop at the first valid triangle.
Recommended for interviews: Interviewers typically expect the greedy sorting solution. The brute force version demonstrates understanding of the triangle condition, but the optimized approach shows algorithmic thinking. Recognizing that sorting reduces the search space from O(n³) to O(n log n) is the key insight. Once sorted, validating only adjacent triplets is both simple to implement and easy to reason about during a whiteboard interview.
Approach 1: Greedy Approach with Sorting
The idea is to sort the array in non-decreasing order and try to form the triangle starting from the largest possible sides. If the largest sides satisfy the triangle inequality, they will produce the largest perimeter. Iterate from the end of the sorted array and check for the triangle inequality condition for the last three elements. If the condition is satisfied, those three can form a triangle, otherwise keep checking the next set of three largest sides.
This Python function begins by sorting the input array. It then iterates backward from the third last element, checking if the current element and the next two largest elements can form a triangle using the triangle inequality rule. If they can, it returns their sum as the largest perimeter.
Complexity
Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) as no additional space is used apart from auxiliary variables.
Approach 2: Brute Force Approach
This approach involves checking all possible combinations of three lengths from the array to see if they form a triangle. If they do, we calculate the perimeter and update the maximum perimeter found so far. This approach is less efficient due to its combinatorial nature but demonstrates the basic principle of checking all potential solutions.
This Python brute force solution checks every triplet of indices to see if they can form a triangle by satisfying the triangle inequality. If they can, it potentially updates the maximum perimeter result.
Complexity
Time Complexity: O(n^3), as it evaluates all combinations of three elements. Space Complexity: O(1), requiring constant additional space.
Approach 3: Sorting + Greedy
Suppose the three sides of the triangle are a leq b leq c. The triangle has non-zero area if and only if a + b \gt c.
We can enumerate the largest side c, then select the two largest remaining sides a and b. If a + b \gt c, a triangle with non-zero area can be formed, and its perimeter will be the largest possible; otherwise, continue to enumerate the next largest side c.
The time complexity is O(n log n), and the space complexity is O(log n), where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(1) as no additional space is used apart from auxiliary variables. |
| Brute Force Approach | Time Complexity: O(n^3), as it evaluates all combinations of three elements. Space Complexity: O(1), requiring constant additional space. |
| Sorting + Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n³) | O(1) | Useful for understanding the triangle inequality and validating logic on small inputs |
| Greedy with Sorting | O(n log n) | O(1) | Best practical solution; sort once then scan from the largest sides |
Video Solution
Largest Perimeter Triangle | Easy Explanation | Leetcode 976 | codestorywithMIK • codestorywithMIK • 10,369 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Largest Perimeter Triangle easy or hard?
Largest Perimeter Triangle Python/Java solution
How to solve Largest Perimeter Triangle in O(n)?
What is the best approach for Largest Perimeter Triangle?
Is Largest Perimeter Triangle asked at Google/Amazon/Meta?
What data structure is used in Largest Perimeter Triangle?
What is the time complexity of Largest Perimeter Triangle?
Ready to solve this problem?
Practice Largest Perimeter Triangle with our built-in code editor and test cases.
Practice on FleetCode