A different way to solve this problem


  • 0

    Most solutions try to compare nums[i] with nums[i-1] directly. Why don't we think it in a different way. We can check the differences between nums.

    Let diff = nums[i] - nums[i-1]
    Let preDiff = nums[i-1] - nums[i-2]

    If diff < 0, we have a down side and one element (either nums[i-1] or nums[i]) must be modified.

    We try to modify nums[i-1] first. It can be modified if and only if nums[i] - nums[i-2] >= 0.
    We can transform it to:
    nums[i] - nums[i-2] >= 0
    ==> nums[i] - nums[i-1] + nums[i-1] - nums[i-2] >= 0
    ==> diff + preDiff >= 0
    ==> diff >= -preDiff

    So, if diff >= -preDiff, we can modify nums[i-1]. Otherwise, we have to modify nums[i]. The best/smallest value is nums[i-1].

    Here is the code:

        public boolean checkPossibility(int[] nums) {
            int count = 0, preNum = nums[0], preDiff = Integer.MAX_VALUE;
            for(int i = 1; i < nums.length; i++) {
                int diff = nums[i] - preNum;
                if (diff < 0 && count++ > 0) return false;
                preNum = diff >= -preDiff ? nums[i] : nums[i-1];
                preDiff = Math.max(0, diff);
            }
            return true;
        }
    

Log in to reply
 

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