Find largest perimeter of a triangle

Companies:
  • Bloomberg Interview Questions
  • ByteDance Interview Questions

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)
Scroll to Top