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:
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.
Once I understand that, I tried to improve it via maintaining a global state during the scanning, as alg2:
# alg 2 cur_maxval= nums # 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|
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
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
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
i+1th element. And we don’t know which might result a non-decreasing array, so we test both cases.