# Think Reversely - from the LeetCode 665th Problem

`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:

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.