Non-Decreasing Array is the 665th problem in LeetCode: Non-Decreasing Array.

Even though it’s categorized in easy-class, its accepted rate is only 20%. It seems easy at first glance, but there are lots of corner cases if following the gut feeling.

The problem as I quote 1:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element. We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

A First Thought

The first thought comes into my mind is to scan the array linearly, if found that one value is larger than its right neighbor, mark it as decreasing. And if it occurs more than once, the whole array does not satisfy the question condition. The pseudo-code:

# alg 1
count = 0
for elet in array:
	if elet > its right neighbor:
		count++
	if count > 1:
		return False
	return True

However, I realize that the above algorithm only considers local scenarios (a value and its right neighbor), it misses considering global scenarios. For example:

Fig.1 example 1: input [1,2,4,1,2]
Fig.1 example 1: input [1,2,4,1,2]

When alg1 scans point C, it marks it as decreasing due to C’s value is larger than D’s. Then alg1 returns True due to it’s the only decreasing case. However, the example doesn’t satisfy the question condition, since B’s value is also larger than D’s.

Second Thought

Once I understand that, I tried to improve it via maintaining a global state during the scanning, as alg2:

# alg 2
cur_maxval=  nums[0] # current maximum element found
fdecrease = False    # flag indicates if found a decreasing elet first time

for idx, val in enumerate(nums[:-1]):
	val_rnbr = nums[idx+1]  # right neighbor

	if cur_maxval > val:
		if fdecrease == True:
			return False

	if val <= val_rnbr:
		if cur_maxval < val_rnbr:
			cur_maxval = val_rnbr 
	else:
		if fdecrease == False:  # first time found decreasing case
			fdecrease = True
		else:
			return False
return True

The basic idea of alg2 is not only considering local situations, but also taking care of global situations by keeping the max value of legitimate scanned elements. For example: input [1,2,4,1,2],

  Scanned Element Current Maximum
A 1 1
B 2 2
C 4 4
D 1 4
E 2 4

When alg2 scan A, B and C, it increases the current maximum to 4. Then it keeps scanning D and E, but it maintains 4 due to it records the non-decreasing trend. It finds the maximum is larger than D and E’s values. Thus the input list does not satisfy the question condition and returns false.

Alg2 seems promising, but it fails input [4,2,3]. That is, when alg2 first scans 4, it sets its current maximum value to 4, then it scans 2 and 3, since they are both smaller than the current maximum value. alg2 will return false. However, the input actually satisfies the question condition if modifies the 4 value.

Final Thought

Fails of first and second thoughts make me realize that there are lots of corner cases to handle if thinking it forwardly, and it finally inspires me thinking it reversely, as:

# alg3
    def checkPossibility_remvone(self, nums):
        for idx, val in enumerate(nums[:-1]):
            val_rnbr = nums[idx+1]
            if val > val_rnbr:
                return False
        return True

    def checkPossibility(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        for idx, val in enumerate(nums[:-1]):
            val_rnbr = nums[idx+1]  # right neighbor
            if val > val_rnbr:
                nums_del_large = nums[:]
                del nums_del_large[idx]

                nums_del_small = nums[:]
                del nums_del_small[idx+1]

                return (self.checkPossibility_remvone(nums_del_large) or 
                        self.checkPossibility_remvone(nums_del_small) )
        return True

alg3 is straight forward. Function checkPossibility scans the given array linearly, if found that a element’s value is larger than its right neighbor’s, such that num[i] > num[i+1], it removes either the ith or i+1th element of the array.

The reason of remove is because the question allows to modify at most one element. If we modify the ith element, it actually indicates the ith element won’t affect the non-decreasing property of the array. Then we test if the remaining array satisfies the property.

One more thing is since we can remove either the ith or i+1th element. And we don’t know which might result a non-decreasing array, so we test both cases.