JAVA O(N) easy and no modifying


  • 2
    class Solution {
        public boolean checkPossibility(int[] nums) {
            int count = 0;
            for (int i = 0; i < nums.length - 1; i++)
                if (!(nums[i] <= nums[i + 1])) {
                    if (count > 0)
                        return false;
                    if (i - 1 >= 0 && i + 2 < nums.length && (nums[i] > nums[i + 2] && nums[i + 1] < nums[i - 1]))
                        return false;
                    count++;
                }
            return true;
        }
    }
    

    Find each downtick.

    • If there are more than one downtick, return false;
    • If you are at your first downtick, but it's one that cannot be erased by modifying only one endpoint of that downtick, then return false;

    What is a downtick that cannot be erased by modifying only one endpoint? If the downtick is at the indices i, i+1, then after modifying, we hope that all four of i-1, i, i+1, i+2 falls into the same range as delimited by i-1 and i+2. But we can only modify one of i, i+1, so if both i, i+1 are out of the range described above, then this downtick is beyond remedy, we return false; Otherwise, just increment count and move on.


Log in to reply
 

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