JAVA solution with explanation, O(n) time ~22ms


  • 0

    To solve the problem we have two cases to keep in mind:

    1. Peak is the very first element. E.g. {4, 2, 3} - we can substitute 4(peak element) with value 2 then sequence turns to increasing {2, 2, 3}. For that case we don’t have to override it, assumption is enough.
    2. Peak is in the middle. E.g. {3, 4, 2, 3} - we substitute element 4(peak) with value 2 {3, 2, 2, 3} the sequence still has a peak at the beginning. To eliminate this case we have to do extra check with the previous element. We do it with next condition check: "if ((i > 1) && (nums[i] < nums[i-2]))”

    In both cases we increment the “count" variable, that stores all peaks that we found traversing the array.
    The algorithm has O(n) time complexity and O(1) space complexity.

    public boolean checkPossibility(int[] nums) {
            int count = 0;
            // we exit the loop if number of peaks exceeded 1
            for (int i = 1; i < nums.length && count <= 1; i++) {
                if(nums[i] < nums[i - 1]) {
                    if ((i > 1) && (nums[i] < nums[i - 2])) {
                        nums[i] = nums[i - 1];
                    }
                    count++;
                }
            }
            return count <= 1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.