Leetcode: Largest Perimeter Triangle

Largest Perimeter Triangle



Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/largest-perimeter-triangle
// Basic Ideas: Sort + Greedy
// Complexity: Time O(n*log(n)), Space O(1)
import "sort"
func largestPerimeter(A []int) int {
    sort.Ints(A)
    for i:=len(A)-1; i>=2; i-- {
        if A[i-2] + A[i-1] > A[i] {
            return A[i-2]+A[i-1]+A[i]
        }
    }
    return 0
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.