O(n) no modified input (java)


  • 0
    S

    two possible go up from left or go down from right

    class Solution {
        public boolean checkPossibility(int[] nums) {
            // go up from left
            // or go down from right
            int count1 = 0;
            int max = nums[0];
            for (int i = 0; i < nums.length -1; i++) {
                max = Math.max(max, nums[i]);
                if (max > nums[i+1]) {
                    count1 ++;                
                }
            }
            if (count1 <= 1) return true;
            int count2 = 0;
            int min = nums[nums.length -1];
            for (int i = nums.length -1; i > 0; i--) {
                min = Math.min(min, nums[i]);
                if (min < nums[i-1]) {
                    count2 ++;                
                    if (count2 > 1) return false;
                }
            }
            if (count2 <= 1) return true;
            else return false;
        }
    }
    

Log in to reply
 

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