Maximum Perimeter Triangle With The Greedy Approach
Understanding the greedy algorithm
Let’s think of an array of stick-lengths, find which three sticks form a non-degenerate triangle such that:
- the triangle has a maximum perimeter
- if there are two or more combinations with the same value of maximum perimeter, output the one with the longest side.
- Output -1 if not possible
Are you confused about the non-degenerate triangle?
If a, b and c are the sides of the triangle, and if the following 3 conditions are true, then it is a non-degenerate triangle.
a + b > c
a + c > b
b + c > aFor example, assume there are stick lengths sticks = [ 1,3,5,10,4,2]. The triplet (1,2,3) will not form a triangle. Neither (4,5,6) will or (2,3,5), so the problem is reduced to (2,3,4) and (3,4,5). The longer perimeter is (3,4,5) =12 .
So many conditions, but this is really easy to solve.
From all the possible triplets, check for the given conditions and keep track of the maximum ones. In the end, output the triplet with the longest side. Yes. Correct. But there will be a problem…
The time complexity of this approach will be O(n³).
We can surely do better.
Forming and checking for all the triplets makes you do a lot of unnecessary work. How could you be sure that once you’ve checked for a particular number in the triplet, you should not consider evaluating other triplets with that number?
Would sorting help?
Take the following examples along with you:
ARRAY OUTPUT
1, 1, 1, 3, 3 1, 3, 3
1, 1, 1, 2, 3 ,5 1, 1, 1
1, 2, 3 -1Suppose that I have a sorted array in Increasing order:
1, 2, 3, 4, 7, 8
consider the triplet 4, 7, 8 as a, b, c, Here a ≤ b ≤ c
Therefore b+c would definitely be more than a and a+c would be definitely more than b.
What remains is we need to check if a+b > c. Then there will be two situations
a+b is more than c:
Then for sure, we have the triplet that satisfies the given conditions. But should we search for more triplets in order to get the maximum perimeter? Isn’t this the maximum possible perimeter?
Because any other triplet will be formed by the numbers before these and would thus obviously form a smaller sum. Thus we start from the maximum number in the sorted array, consider it’s triplet if it satisfies the conditions as the maximum perimeter. In our case 4 + 7 > 8, thus the solution is [4, 7, 8]
a+b is not more than c:
Consider 1, 2, 3, 3, 5, 8. Here 3 + 5 is not more than 8. And we do not need to check other combinations along with 8? Because all of the other combinations would be
8, 5, 3
8, 5, 2
8, 5, 1
8, 3, 3
8, 3, 2
8, 3, 1Then just move to the next element and check for its corresponding triplet. In our case, the next would be [3, 3, 5]
Which satisfies a point.
Algorithm
1. Sort the array in increasing order.2. Starting from index i = array.length - 3.3. If sides[i] + sides[i+1] > sides[i+2], then
output these three sides as result triplet and
break from the loop. if not continue the loop until i = 0.4. If no triplet is found, output -1.
Implementation
Time complexity
O(N log N)
where N is the number of elements in the array
Space complexity
O(1)
We are not using any data structure to store anything.
Summary
When we consider time complexity, in the normal approach it takes O(n³), and the greedy approach takes only O(N log N). Therefore the greedy approach is a very efficient way of solving minimization and maximization problems. Hope this article helped you to develop your knowledge about greedy algorithms. Let’s meet with another interesting article in the near future.
Thank you for reading and Happy Learning 🙌😊
