Leetcode 976. Largest Perimeter Triangle
Problem Explanation:
We are given an array of integers, where each integer represents a stick's length. We want to choose three sticks from the array and try to form a triangle. The problem statement asks us to return the largest possible perimeter (which is the sum of the lengths of the sides) of a non-zero area triangle that we can form from the given sticks. If we cannot form any triangle, return 0.
A triangle can only form if the sum of the lengths of the two shorter sides is greater than the length of the longest side.
For example, if the input array is [3,2,3,4], we sort it to get [2,3,3,4]. We start checking from the last three elements - if they can form a triangle, their sum would be largest possible perimeter because the array is sorted. The last three elements are [3,3,4] and they can form a triangle because 3+3 > 4. So, their sum i.e., 10 is returned.
Solution Approach:
The solution uses a sorting algorithm to firstly sort the length's array. The reason to sort the lengths is that it simplifies the problem - once sorted, we know the combination of the largest three lengths is likely to form the largest perimeter. However, it might not always be possible to form a triangle from those lengths. Forming a triangle is only possible if the sum of lengths of the two smaller sides is greater than the longest side. If this condition is not fulfilled, we ignore the longest side and try forming a triangle with the next largest lengths.
Solution in Python:
1 2python 3class Solution: 4 def largestPerimeter(self, A): 5 A.sort() 6 for i in range(len(A)-3, -1, -1): 7 if A[i] + A[i+1] > A[i+2]: 8 return A[i] + A[i+1] + A[i+2] 9 return 0
Solution in Java:
1 2java 3class Solution { 4 public int largestPerimeter(int[] A) { 5 Arrays.sort(A); 6 for(int i=A.length-3; i >= 0; i--){ 7 if(A[i] + A[i+1] > A[i+2]) 8 return A[i] + A[i+1] + A[i+2]; 9 } 10 return 0; 11 } 12}
Solution in JavaScript:
1 2javascript 3var largestPerimeter = function(A) { 4 A.sort((a, b) => a - b); 5 for(let i = A.length - 3; i >= 0; i--) { 6 if(A[i] + A[i+1] > A[i+2]) { 7 return A[i] + A[i+1] + A[i+2]; 8 } 9 } 10 return 0; 11};
Solution in C++:
1
2c++
3class Solution {
4public:
5 int largestPerimeter(vector<int>& A) {
6 sort(A.begin(), A.end());
7 for (int i = A.size() - 3; i >= 0; --i)
8 if (A[i] + A[i+1] > A[i+2])
9 return A[i] + A[i+1] + A[i+2];
10 return 0;
11 }
12};
Solution in C#:
1 2csharp 3public class Solution { 4 public int LargestPerimeter(int[] A) { 5 Array.Sort(A); 6 for (int i = A.Length - 3; i >= 0; i--) 7 if (A[i] + A[i+1] > A[i+2]) 8 return A[i] + A[i+1] + A[i+2]; 9 return 0; 10 } 11}
Final remarks:
In conclusion, the problem of finding the largest perimeter of a triangle that can be formed using an array of integers representing stick lengths can be solved using a sorting algorithm. By sorting the array in ascending order, we can start checking from the last three elements - if they can form a triangle, their sum would be the largest possible perimeter because the array is sorted. If these three lengths can't form a triangle, we discard the longest one and consider the next largest lengths until we find three lengths that fulfill the triangle inequality or until there are less than three lengths left. If no triangle can be formed, the function returns 0.
One important thing to consider while implementing this solution is the efficiency of the sorting algorithm used. A more efficient sorting algorithm would result in a faster solution.
Solutions for this problem have been provided in Python, Java, JavaScript, C++, and C#. This same general approach could be applied in any other programming language that supports sorting of arrays or lists.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.