Reading time: 20 minutes | Coding time: 5 minutes

Given an array of integers, find which three elements form a non-degenerate triangle such that:

• the triangle has maximum perimeter
• if there are two or more combinations with same value of maximum perimeter, output the one with the longest side. Output -1 if not possible

First of all, what’s a 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>a

Phew! So many conditions! But honestly, this is really easy to solve.
From all the possible triplets, check for the given conditions and keep track of the maximum ones. At the end, output the one with the longest side. Yes. Correct.
The time complexity of this approach will be O(n^3). We can surely do better.

Here’s the thing: 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. Try to think about this. Let me give you a hint:
Would sorting help?
Take the following examples along with you:

Read ahead only after you’ve had a thought on this for at least 10 minutes.

Understand the following things:

Suppose that I have a sorted array in decreasing order:

8, 5, 4, 3, 2, 1

consider the triplet 8, 5, 4 as a, b, c
Here a>=b>=c
Therefore a+c would definitely be more than b and a+b would be definitely more than c.

What remains is we need to check if b+c > a. Two cases arise.

1. b+c is more than a:

If this is the case, then for sure we have the triplet that satisfies the given conditions. But you tell me, should we search 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 after 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, it’s the maximum perimeter. In our case 5+4 > 8, thus the solution is [8, 5, 4]

2. b+c is not more than a:

Consider 8, 5, 3, 3, 2, 1. Here 5+3 is not more than 8. But do you think we should really check for other combinations along with 8? No, right? 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, 1

And some other…...
You should notice that as we have sorted the array in decreasing order, the other two numbers sum would be less than or equal to 5+3. Thus, even their sum would not be greater than a. The condition won’t be satisfied then as well. So no need to check for them. Just move to the next element and check for its corresponding triplet. In our case the next would be [5, 3, 3]
Which satisfies a point.

Algorithm

1. Sort the sides array in increasing order.
   (You could also sort in decreasing order and accordingly manipulate the for loop and conditions)
2. Starting from last element at index i
   a. if sides[i-2]+sides[i-1]>sides[i], then
   output these three sides as result triplet and
   break from the loop.
3. If no triplet is found, output -1.

Simple right? Try to code this. You just have to check for the conditions.

Implementation

Following is the code in Java to this problem:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class PerimeterTriangle {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        br.readLine();
	//no. of elements in array
        int n = Integer.parseInt(br.readLine());
        int[] sides = new int[n];
        String[] input;
        input = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            sides[i] = Integer.parseInt(input[i]);
        }
        Arrays.sort(sides);
        boolean flag = false;
//starting from end, because we have sorted in //ascending order and we want the max element //first, you could also sort in descending order //and start from i=0
        for(int i=n-1; i>=2; i--){
            if(sides[i-2]+sides[i-1]>sides[i]){
                System.out.println(sides[i-2]+" "+sides[i-1]+" "+sides[i]);
                flag = true;
                break;
            }
        }
        if(flag==false){
            System.out.println("-1");
        }
}
}

Complexity

Time complexity
O(nlogn)
where n is the number of elements in the array

Space complexity
O(1)
We are not using any data structure to store anything.