Non-decreasing Array

'''
We traverse the array and look for violations: nums[i] < nums[i-1]

At a violation, there are only two possible fixes:
1. Reduce nums[i-1]
2. Increase nums[i]

We prefer to keep the smaller value unchanged if possible because smaller values are safer in a non-decreasing array and give more flexibility for upcoming elements.

So first we try to keep nums[i] unchanged (since it is smaller).
To do that safely, we check:

nums[i] >= nums[i-2]

If true, then lowering nums[i-1] will still keep the left side sorted, so we do:

nums[i-1] = nums[i]

Otherwise, lowering nums[i-1] would create another violation on the left side, so we have no choice except:

nums[i] = nums[i-1]
'''
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        cnt=0
        for i in range(1,len(nums)):
            if nums[i-1]>nums[i]: #violation
                cnt+=1
                if cnt>1:
                    return False
                if i<2 or nums[i-2]<=nums[i]:
                    nums[i-1]=nums[i]
                else:
                    nums[i]=nums[i-1]
        return True