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

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

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.

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```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```
```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)

 ```1 2 3 4 5 6 7 8 9 10 11 ``` ```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```
```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).

 ```1 2 3 4 5 6 7 ``` ```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```
```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```

GD Star Rating