Maximum Perimeter Triangle HackerRank Solution

Maximum Perimeter Triangle HackerRank Solution
Source : https://www.hackerrank.com/challenges/maximum-perimeter-triangle

Given an array of stick lengths, use of them to construct a non-degenerate triange 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.

Constraints

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

51 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

31 2 3

Sample Output 1

-1

Explanation 1

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

Sample Input 2

61 1 1 2 3 5

Sample Output 2

1 1 1

Explanation 2

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

Source : https://www.hackerrank.com/challenges/maximum-perimeter-triangle

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Arrays;
	import java.util.Collections;
	// Time complexity: O(n log n)
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int N = scan.nextInt();
	Integer [] stick = new Integer[N];
	for (int i = 0; i < N; i++) {
	stick[i] = scan.nextInt();
	}
	scan.close();
	findTriangle(stick);
	}
	/* Greedy Approach: Try to use the biggest sticks first */
	private static void findTriangle(Integer [] stick) {
	Arrays.sort(stick, Collections.reverseOrder());
	for (int i = 0; i < stick.length - 2; i++) {
	if (stick[i] < stick[i+1] + stick[i+2]) {
	System.out.println(stick[i+2] + " " + stick[i+1] + " " + stick[i]);
	return;
	}
	}
	System.out.println(-1);
	}
	}