Non decreasing array logic fail

February 16, 2022

I am trying to solve the non decreasing array problem

Given an array nums with n integers, check if it could become non-decreasing by modifying at most one element.

Non-decreasing is defined as follows: if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n – 2).

Here is my solution that works for [4,2,3] but does not for [-1,4,2,3]

According to my logic when the pointer is at 2 for [-1,4,2,3],the if block will be executed at i-2(-1) is less than i(2) and the value of 4 will chnage to 2 but apparently that does not happen.

#nums=[4,2,3]
nums=[-1,4,2,3]
count=0
for i in range(len(nums)):
    if nums[i] < nums[i-1]:
        if (i==1 or nums[i-2]<=nums[i]):
            nums[i-1]=nums[i]
            count+=1
        else:
            nums[i]=nums[i-1]
            count+=1
            
print(count<=1)

Any help will be greatly appreciated.

>Solution :

The main issue with your code:

You loop i over range(len(nums)), so it starts at 0, which means the first condition nums[i] < nums[i-1] evaluates to nums[0] < nums[-1] and I don’t think you want to compare the first element to the last element at all.

For the rest, when you find an issue (i.e. nums[i] < nums[i-1]), you check if previous number could be lowered to sit between the current number and the number before the previous number, and then set it to the current number; if that doesn’t work, you just lower the current number to be equal to the previous number and count either case.

You keep checking even if count is already 2 or greater though, which is very inefficient for long series. And since you increase count in either case, that increment could sit outside the conditional blocks.

So your code becomes:

nums = [-1,4,2,3]
count = 0
for i in range(1, len(nums)):
    if nums[i] < nums[i-1]:
        if (i == 1 or nums[i-2] <= nums[i]):
            nums[i-1] = nums[i]
        else:
            nums[i] = nums[i-1]
        if (count := count + 1) > 1:  # parentheses not needed, but for clarity
            break
            
print(count<=1)

Note that your solution will only work for max 1 flaw though. Turned into a function, consider this:

def almost_non_decreasing(nums, max_flaws=1):
    count = 0
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            if (i == 1 or nums[i - 2] <= nums[i]):
                nums[i - 1] = nums[i]
            else:
                nums[i] = nums[i - 1]
            if (count := count + 1) > max_flaws:
                return False
    return True


print(almost_non_decreasing([-1, 4, 2, 3]))
print(almost_non_decreasing([5, 4, 2, 3]))
print(almost_non_decreasing([5, 4, 2, 3], 2))

The last one prints False, even though [2, 2, 2, 3] would work, but your solution will only try [4, 4, 4, 3] and then fail when it needs to change the final 3 as well.