Find largest perimeter of a triangle | Largest Perimeter Triangle | Leet Code
Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.
If it is impossible to form any triangle of non-zero area, return 0.
Example 1:
Input: [4,6,3]
Output: 13
Example 2:
Input: [1,2,4]
Output: 0
Solution:
This problem is very simple if you know mathematics behind it.
Let’s say the sidelength of a given triangle are a, b, c and also a≤b≤c.
The necessary condition for these lengths to form a triangle is a + b > c.
By this approach we will solve the problem.
Implementation:
Java:
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);
for (int i = A.length - 3; i >= 0; --i)
if (A[i] + A[i+1] > A[i+2])
return A[i] + A[i+1] + A[i+2];
return 0;
}
}
Complexity Analysis:
- Time Complexity: O(nlogn)
- Time Complexity: O(1)
