Non-decreasing Array

Patrick Leaton
Published: May 29, 2021, 6:30 p.m.
Problem Description

Given an array nums 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 nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

 

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

 

Constraints:

  • 1 <= n <= 10 ^ 4
  • - 10 ^ 5 <= nums[i] <= 10 ^ 5

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        bad = None
        for i in range(len(nums) - 1):
            if nums[i] > nums[i+1]:
                if bad is not None:
                    return False
                bad = i + 1
 
        return bad is None or \
               bad == 1 or \
               bad == len(nums)-1 or \
               nums[bad-2] <= nums[bad] or \
               nums[bad-1] <= nums[bad+1]

Problem Explanation

The problem description is saying that we can change the value of one element and see if the array becomes non-decreasing afterward.  Recall that non-decreasing means that consecutive numbers are either increasing or equal.

To solve this, we can see where the bad element is that's wrecking the array's non-decreasing order, then see if we could modify the value to fix the order by checking between a few conditions that the index would need to satisfy if we were to restore the non-decreasing order.

We will start by initializing the bad value variable.

        bad = None

 

We will then traverse the array and in each iteration, we will check if the next number is less than the current one.

        for i in range(len(nums) - 1):
            if nums[i] > nums[i+1]:

 

If the bad value has already been set in a previous iteration, we would have to edit two values to fix the non-decreasing order.  
If that is the case, we will return false.

                if bad is not None:
                    return False

 

Otherwise, we will mark the bad index.

                bad = i + 1

 

Here is where we will check if the order is valid, or if we could make it valid by seeing if a handful of boolean conditions would return true.

If bad is none, the order is valid and we won't have to modify anything.

        return bad is None or \

 

If bad is index one, then we would have an input like this:

[1,0,2,3]

We could just change the element at index zero to be less or equal and the order would be fixed.

[-1,0,2,3]

               bad == 1 or \

 

If bad is the last index, then we would have an input like this:

[1,2,3,2]

We could just change the element at the last index to be greater or equal to the previous element and the order would be fixed.

[1,2,3,4]

               bad == len(nums)-1 or \

 

If the element two indices behind bad is less than or equal to bad, then we would have an input like this:

[0,2,1,3]

We can replace the element at the index in-between these two indices to be less than or equal to bad and the order would be fixed.

[0,1,1,3]

               nums[bad-2] <= nums[bad] or \

 

If the element to the left of bad is less than or equal to the element to the right of bad, then we would have an input like this:

[1,0,2,3]

We can change bad to be greater than or equal to the previous number, but less than or equal to the next number, and the order would be fixed.

[1,1,2,3]

               nums[bad-1] <= nums[bad+1]