Largest Perimeter Triangle

Easy

#0930Time: O(n^3), where n is the number of elements in `nums`. This is because of the three nested loops required to check every combination of three sides.Space: O(1), as we only use a constant amount of extra space for variables.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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 <= 10⁴
1 <= nums[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible combination of three side lengths from the input array. We use three nested loops to select three distinct numbers. For each combination, we check if they can form a valid triangle using the Triangle Inequality Theorem.

Algorithm

Initialize maxPerimeter to 0.
Use three nested loops to iterate through all unique triplets (i, j, k).
Let the sides be a = nums[i], b = nums[j], c = nums[k].
Check if a, b, and c can form a valid triangle using the triangle inequality: a + b > c, a + c > b, and b + c > a.
If they form a valid triangle, update maxPerimeter = max(maxPerimeter, a + b + c).
Return maxPerimeter after the loops complete.

Walkthrough

The Triangle Inequality Theorem states that for three side lengths a, b, and c to form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side (a + b > c, a + c > b, and b + c > a).

The algorithm proceeds as follows:

Initialize a variable maxPerimeter to 0.
Use three nested loops to pick three distinct indices i, j, and k from the array.
For each triplet of numbers (nums[i], nums[j], nums[k]), check if they satisfy all three conditions of the triangle inequality.
If they form a valid triangle, calculate their sum (perimeter) and update maxPerimeter if this new perimeter is larger than the current maxPerimeter.
After checking all possible triplets, the value stored in maxPerimeter is the answer. If no triangle could be formed, it will remain 0.

1class Solution {2    public int largestPerimeter(int[] nums) {3        int n = nums.length;4        int maxPerimeter = 0;5        for (int i = 0; i < n - 2; i++) {6            for (int j = i + 1; j < n - 1; j++) {7                for (int k = j + 1; k < n; k++) {8                    int a = nums[i];9                    int b = nums[j];10                    int c = nums[k];11                    if (a + b > c && a + c > b && b + c > a) {12                        maxPerimeter = Math.max(maxPerimeter, a + b + c);13                    }14                }15            }16        }17        return maxPerimeter;18    }19}

Complexity

Time

O(n^3), where n is the number of elements in `nums`. This is because of the three nested loops required to check every combination of three sides.

Space

O(1), as we only use a constant amount of extra space for variables.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem for small inputs.

Cons

Very inefficient due to its cubic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

A much more efficient approach is to first sort the array. To maximize the perimeter, we should use the largest possible side lengths. By sorting the array, we can simplify the triangle check and greedily search for the largest perimeter triangle starting from the largest elements.

Algorithm

Sort the input array nums in ascending order.
Iterate backwards from i = n-1 down to 2.
For each i, consider the triplet (nums[i-2], nums[i-1], nums[i]).
Check if nums[i-2] + nums[i-1] > nums[i].
If the condition is true, this triplet forms the largest possible perimeter triangle. Return nums[i-2] + nums[i-1] + nums[i].
If the loop finishes, no valid triangle can be formed. Return 0.

Walkthrough

The key insight is based on the Triangle Inequality Theorem. If we have three side lengths a, b, and c such that a <= b <= c, we only need to check if a + b > c. The other two inequalities (a + c > b and b + c > a) will always hold true since c is the largest side.

To find the largest perimeter, we should prioritize using the largest numbers available. This leads to a greedy strategy.

The algorithm is as follows:

Sort the input array nums in non-decreasing order.
Iterate backwards from the end of the sorted array, from index i = n-1 down to 2.
In each iteration, consider the triplet of sides (nums[i-2], nums[i-1], nums[i]). These are three consecutive elements.
Check if they form a valid triangle. Since the array is sorted, nums[i-2] <= nums[i-1] <= nums[i]. We only need to check if nums[i-2] + nums[i-1] > nums[i].
If this condition is true, we have found a valid triangle. Because we are iterating from the largest elements downwards, this must be the triangle with the largest possible perimeter. Any other valid triangle would involve smaller sides, resulting in a smaller perimeter. We can immediately return the perimeter nums[i-2] + nums[i-1] + nums[i].
If the loop completes without finding any such triplet, it means no valid triangle can be formed. In this case, we return 0.

1import java.util.Arrays;2 3class Solution {4    public int largestPerimeter(int[] nums) {5        Arrays.sort(nums);6        for (int i = nums.length - 1; i >= 2; i--) {7            // Let nums[i] be the longest side 'c'8            // Let nums[i-1] be 'b' and nums[i-2] be 'a'9            // Since the array is sorted, a <= b <= c.10            // We only need to check if a + b > c.11            if (nums[i - 2] + nums[i - 1] > nums[i]) {12                return nums[i - 2] + nums[i - 1] + nums[i];13            }14        }15        return 0;16    }17}

Complexity

Time

O(n log n), where n is the number of elements in `nums`. The sorting operation takes O(n log n) time, and the subsequent linear scan takes O(n) time.

Space

O(log n) or O(n), depending on the space complexity of the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which has an average space complexity of O(log n).

Trade-offs

Pros

Highly efficient and optimal solution.
Simple logic after sorting.
The greedy choice of checking the largest elements first is guaranteed to find the maximum perimeter.

Cons

The time complexity is bound by the sorting algorithm.

Solutions

Solution

1class Solution { public int largestPerimeter ( int [] nums ) { Arrays . sort ( nums ); for ( int i = nums . length - 1 ; i >= 2 ; -- i ) { int c = nums [ i - 1 ] + nums [ i - 2 ]; if ( c > nums [ i ]) { return c + nums [ i ]; } } return 0 ; } }

1class Solution { public: int largestPerimeter ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); for ( int i = nums . size () - 1 ; i >= 2 ; -- i ) { int c = nums [ i - 1 ] + nums [ i - 2 ]; if ( c > nums [ i ]) return c + nums [ i ]; } return 0 ; } };

1class Solution : def largestPerimeter ( self , nums : List [ int ]) -> int : nums . sort () for i in range ( len ( nums ) - 1 , 1 , - 1 ): if ( c : = nums [ i - 1 ] + nums [ i - 2 ]) > nums [ i ]: return c + nums [ i ] return 0

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem