We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Maximum Perimeter Triangle
  5. Discussions

Maximum Perimeter Triangle

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 270 Discussions, By:

votes

Please Login in order to post a comment

  • AbhishekVermaIIT
    6 years ago+ 32 comments

    There's no need to complicate it, here's a simple Python solution :

    n = int(input())
    A = sorted(int(i) for i in input().split())
    
    i = n-3
    while i >= 0 and (A[i] + A[i+1] <= A[i+2]) :
        i -= 1
    
    if i >= 0 :
        print(A[i],A[i+1],A[i+2])
    else :
        print(-1)
    

    Logic : Select the longest possible side such that it can form a non-degenerate triangle using the two sides "just smaller" than it.

    It fulfills all other conditions. If no such selection is possible, then no non-degenerate triangle exists.

    Informative Tweets for Inquisitive Minds

    189|
    Permalink
    View more Comments..
  • tao_zhang
    6 years ago+ 5 comments

    Java solution:

    import java.util.*;
    
    public class Solution {
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            scanner.close();
            Arrays.sort(a);
            int x, y, z;
            for(x=n-3, y=n-2, z=n-1; a[x]+a[y]<=a[z]; x--, y--, z--){
                if(x==0) {
                    System.out.print(-1);
                    return;
                }
            }
            System.out.printf("%d %d %d", a[x], a[y], a[z]);
        }
    }
    
    23|
    Permalink
    View more Comments..
  • RodneyShag
    5 years ago+ 0 comments

    Java solution - passes 100% of test cases

    From my HackerRank solutions.

    Hint: Sort the sticks

    Time complexity: O(n log n)

    import java.util.Scanner;
    import java.util.Arrays;
    import java.util.Collections;
    
    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);
        }
    }
    

    Let me know if you have any questions.

    15|
    Permalink
  • Ardiya
    5 years ago+ 4 comments

    Non-generate triangle happens when a side of triangle exceed the sum of the other 2 sides. Imagine a triangle with side of 1, 1, and 2; it becomes a line, not a triangle :p. This is the function check the non-generate with input of integer a, b, c where a <= b <= c:

    bool isvalid(int a, int b, int c){
        return a+b>c;
    }
    

    then the problem become sorting followed by triangle validation.

    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i<n; ++i){
        cin>>v[i];
    }
    sort(v.begin(), v.end(), /* descending */);
    
    for(int i = 2; i<n; ++i){
        if(isvalid(v[i], v[i-1], v[i-2])){
            cout<<v[i]<<" "<<v[i-1]<<" "<<v[i-2]<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
    
    10|
    Permalink
    View more Comments..
  • rasko_leinonen
    4 years ago+ 0 comments

    Java implementation with comments:

    static int[] maximumPerimeterTriangle(int[] s) {
      // Triangle inequality theorem states that
      // for any non-degenerate triangle, the sum 
      // of the lengths of any two sides must be 
      // greater than the length of the remaining 
      // side.
    
      // Sort sticks in ascending order.
      Arrays.sort(s);
      // Reverse sticks in decending order.
      for(int left = 0 ; left < s.length / 2; left++) { 
        int right = s.length - 1 - left;
        int tmp = s[left]; 
        s[left] = s[right]; 
        s[right] = tmp;
      }
      // Go through the sticks in
      // descending order.
      for(int i = 0 ; i < s.length - 2 ; ++i) {
        if (s[i] < s[i+1] + s[i+2]) {
          // This is a non-degenerate triangle.
          // Because we ordered the sticks
          // in descending order this
          // triangle must have the maximum
          // perimeter.
          return new int[] { s[i+2], s[i+1], s[i] };        
        }
      }
      return new int[] { -1 }; 
    }
    
    4|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature