Hackerrank - Maximum Perimeter Triangle Solution

Hackerrank - Maximum Perimeter Triangle Solution

Given an array of stick lengths, use  of them to construct a non-degenerate triangle with the maximum possible perimeter. Print the lengths of its sides as  space-separated integers in non-decreasing order.

If there are several valid triangles having the maximum perimeter:

  1. Choose the one with the longest maximum side.
  2. If more than one has that maximum, choose from them the one with the longest minimum side.
  3. If more than one has that maximum as well, print any one them.

If no non-degenerate triangle exists, print -1.

For example, assume there are stick lengths . The triplet  will not form a triangle. Neither will  or , so the problem is reduced to  and . The longer perimeter is .

Function Description

Complete the maximumPerimeterTriangle function in the editor below. It should return an array of  integers that represent the side lengths of the chosen triangle in non-decreasing order.

maximumPerimeterTriangle has the following parameter(s):

  • sticks: an integer array that represents the lengths of sticks available

Input Format

The first line contains single integer , the size of array .
The second line contains  space-separated integers , each a stick length.


Output Format

Print the lengths of the  chosen sticks as space-separated integers in non-decreasing order.

If no non-degenerate triangle can be formed, print -1.

Sample Input 0

1 1 1 3 3

Sample Output 0

1 3 3

Explanation 0

There are  possible unique triangles:

The second triangle has the largest perimeter, so we print its side lengths on a new line in non-decreasing order.

Sample Input 1

1 2 3

Sample Output 1


Explanation 1

The triangle  is degenerate and thus can't be constructed, so we print -1 on a new line.

Sample Input 2

1 1 1 2 3 5

Sample Output 2

1 1 1

Explanation 2

The triangle (1,1,1) is the only valid triangle.

Solution in Python

def maximumPerimeterTriangle(a):
    for i in range(0,len(a)-2):
        if a[i]<a[i+1]+a[i+2]:
            return [a[i+2],a[i+1],a[i]]
    return [-1]
a = sorted(map(int,input().split()), reverse=True)

Note: Sum of any two sides of a triangle is greater than the 3rd side.

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]