Greedy Algorithm to Find the Largest Perimeter Triangle by Sorting

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

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

Sort and be Greedy

The minimal requirement for 3 lengths to become a triangle is that the sum of the minimal two lengths should be larger than the third one (biggest). Let’s say these lengths are sorted in ascending order from the smallest to the largest: a, b and c. It can be certain that a + b should be larger than c i.e. a + b > c

So, the greedy algorithm to find the largest Perimeter triangle is to sort (with O(nlogn) time complexity) these lengths first, then start from the biggest number c, and check if the next two biggest numbers a, and b are valid to form a triangle.

The overall algorithm complexity takes at O(nlogn+n) which is O(nlogn). The space complexity is O(1). Below C++ code implements the greedy algorithm to find the largest perimeter triangle.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(begin(A), end(A));
        for (int i = A.size() - 3; i >= 0; -- i) {
            if (A[i] + A[i + 1] > A[i + 2]) {
                return A[i] + A[i + 1] + A[i + 2];
            }
        }
        return 0;
    }
};

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(begin(A), end(A));
        for (int i = A.size() - 3; i >= 0; -- i) {
            if (A[i] + A[i + 1] > A[i + 2]) {
                return A[i] + A[i + 1] + A[i + 2];
            }
        }
        return 0;
    }
};

And below is the Java version that does the same thing – with slightly different syntax:

1
2
3
4
5
6
7
8
9
10
11

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;        
    }
}

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;        
    }
}

Also Read: Teaching Kids Programming – Largest Perimeter Triangle (Sorting + Greedy Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —