Java code checking deltas, plenty of comments, unlike most up-voted solutions


  • 0
    A
    class Solution {
    public boolean checkPossibility(int[] nums) {
        // algorithm 2017/08/27: at most we have a dip or a bump. A dip is defined as 2-1-3 pattern, and a dump is 2-4-3 pattern
        //  for both dip and bump, there is a decrease; 
        // so the algorithm is to find the n-1 deltas, and we should have at most a single negative delta
        if (null == nums || 2 >= nums.length) {
            return true;    // 0 element, 1 element, 2 elements
        }
        
        int[] deltas = new int[nums.length-1];
        for (int index = 1; index < nums.length; index++) {
            deltas[index-1] = nums[index] - nums[index-1];
        }
        
        // check deltas
        int countNegativeDeltas = 0;
        int indexNegativeDelta = -1;
        for (int index = 0; index < deltas.length; index++) {
            if (deltas[index] < 0) {
                indexNegativeDelta = index;
                countNegativeDeltas++;
            }
        }
        
        if (2 <= countNegativeDeltas) {
            return false;   // at least two decrease
        } else if (0 == countNegativeDeltas) {
            return true;    // no negative
        } else {
            // exactly one decrease
            // if at the either end, then we just simply adjust either end number
            if (0 == indexNegativeDelta || deltas.length-1 == indexNegativeDelta) {
                return true;
            } else {
                // if in the middle, then we simply need to guarantee the number after the dip/bump 
                //  is no smaller than the number before the dip/bump. The two numbers' delta >= 0
                if (deltas[indexNegativeDelta] + deltas[indexNegativeDelta+1] >= 0) {
                    // this is a dip
                    return true;
                } else if (deltas[indexNegativeDelta] + deltas[indexNegativeDelta-1] >= 0) {
                    // this is a bump
                    return true;
                }
            }
            return false;
        }
    }
    

    }


Log in to reply
 

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