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

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:
Input: nums = [2,1,2]
Output: 5

Example 2:
Input: nums = [1,2,1]
Output: 0

Constraints:
3 <= nums.length <= 10^4
1 <= nums[i] <= 10^6

Largest Perimeter Triangle (Brute Force Algorithm)

We can bruteforce all triplets as three sides of a triangle. This takes O(N^3). To validate if 3 sides can form a triangle, we check if the sum of the smallest 2 sides is larger than the biggest one.

class Solution(object):
    def largestPerimeter(self, A):
        ans = 0
        n = len(A)
        for i in range(n):
            for j in range(i):
                for k in range(j):
                    s = sorted([A[i], A[j], A[k]])
                    if s[0] + s[1] > s[2]:
                        ans = max(ans, sum(s))
        return ans

If we sort the sides in ascending order, we know which two are the smallest but still, the time complexity is O(N^3)

class Solution(object):
    def largestPerimeter(self, A):
        ans = 0
        A.sort()
        n = len(A)
        for i in range(n):
            for j in range(i):
                for k in range(j):
                    if A[j] + A[k] > A[i]:
                        ans = max(ans, A[j] + A[k] + A[i])
        return ans

Largest Perimeter Triangle (Sorting + Greedy Algorithm)

We sort the sides in ascending order, then we can greedily check backwards the consecutive three numbers. If it forms a triangle, we immediately return the sum, as it is the largest, otherwise, we shift the window to the left. The time complexity is O(NLogN)

If current three numbers [a, b, c] cannot form a triangle because a plus b is less or equal than c, there isn’t other pairs of (x, y) that sum of it aka x+y is larger than c because c is the current largest unseen value, and a and b are the current largest two sides other than c (the longest side in a triangle).

class Solution(object):
    def largestPerimeter(self, A):
        A.sort()
        for i in range(len(A) - 3, -1, -1):
            if A[i] + A[i+1] > A[i+2]:
                return A[i] + A[i+1] + A[i+2]
        return 0

Also Read Greedy Algorithm to Find the Largest Perimeter Triangle by Sorting

–EOF (The Ultimate Computing & Technology Blog) —