Maximum Perimeter Triangle

  • + 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);
        }