976. Largest Perimeter Triangle #

Problem #

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: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

• 3 <= A.length <= 10000
• 1 <= A[i] <= 10^6

Problem Summary #

Find the lengths of three sides that can form a triangle, and output the longest sum of the three sides, that is, the longest perimeter of the triangle.

Solution Approach #

This problem is also a sorting problem. First sort all the lengths, then search backward starting from the largest side. Find the first index where the sum of any two sides is greater than the third side (satisfying the condition for forming a triangle), then output the sum of these 3 sides. If none is found, output 0.

Code #

package leetcode

func largestPerimeter(A []int) int {
	if len(A) < 3 {
		return 0
	}
	quickSort164(A, 0, len(A)-1)
	for i := len(A) - 1; i >= 2; i-- {
		if (A[i]+A[i-1] > A[i-2]) && (A[i]+A[i-2] > A[i-1]) && (A[i-2]+A[i-1] > A[i]) {
			return A[i] + A[i-1] + A[i-2]
		}
	}
	return 0
}