Maximum Perimeter Triangle

Sort by

recency

|

324 Discussions

|

  • + 0 comments

    This question can easily be solved by sorting the sticks array but when you are likely to only examine the top few elements in the array, I prefer to use a priority queue for faster run time.

    void maxPerimeter(int *sticks, int n, int *ans) {
        heapify(sticks, n);
        ans[2] = sticks[0];
        popTop(sticks, &n);
        ans[1] = sticks[0];
        popTop(sticks, &n);
        ans[0] = sticks[0];
        popTop(sticks, &n);
        while (ans[0] + ans[1] <= ans[2]) {
            if (n == 0) {
                ans[0] = -1;
                return;
            }
            ans[2] = ans[1];
            ans[1] = ans[0];
            ans[0] = sticks[0];
            popTop(sticks, &n);
        }
    }
    
  • + 0 comments
    def maximumPerimeterTriangle(sticks):
        sticks.sort()
        b=sticks[0]+sticks[1]
        a=[0,0,0]
        for i in range(2,n):
            if b>sticks[i]:
                a=[sticks[i-2],sticks[i-1],sticks[i]]
            b=b-sticks[i-2]+sticks[i]
        if a[0]==a[1]==a[2]==0:
            return ['-1']
        else:
            return a
    
  • + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/cP4PLTgC1OE

    vector<int> maximumPerimeterTriangle(vector<int> sticks) {
        sort(sticks.begin(), sticks.end());
        for(int i = sticks.size() - 1; i >= 2; i--){
            if(sticks[i] < sticks[i - 1] + sticks[i - 2]) return {sticks[i - 2], sticks[i -1], sticks[i] };
        }
        return {-1};
    }
    
  • + 0 comments

    My Java solution with o(n log n) time complexity and o(1) space complexity:

    public static List<Integer> maximumPerimeterTriangle(List<Integer> sticks) {
            // find 3 vals that produce the max sum; vals are sorted, and first two sum is greater than 3rd val
            
            //sort array ascending
            Collections.sort(sticks);
            
            //check each max len and if it follows the triangle inequality theorem
            for(int i = sticks.size() - 1; i > 1; i--){
                int maxLen = sticks.get(i);
                int midLen = sticks.get(i - 1);
                int minLen = sticks.get(i - 2);
                if(minLen + midLen > maxLen) return Arrays.asList(minLen, midLen, maxLen);
            }
            return Arrays.asList(-1);
        }
    
  • + 0 comments

    Here is my Python solution!

    def maximumPerimeterTriangle(sticks):
        triangles = []
        for i in range(len(sticks)):
            for j in range(i + 1, len(sticks)):
                for k in range(j + 1, len(sticks)):
                    triangle = [sticks[i] ,sticks[j], sticks[k]]
                    triangle.sort()
                    if sum(triangle[:2]) > triangle[2]:
                        triangles.append([sum(triangle), triangle])
        if triangles:
            return sorted(triangles)[-1][1]
        return ["-1"]