Watch 10 video solutions for Largest Perimeter Triangle, a easy level problem involving Array, Math, Greedy. This walkthrough by codestorywithMIK has 9,373 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 106Problem 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 | 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 |