LeetCode 665: Non-decreasing Array

Problem Restatement

We are given an integer array nums.

We need to check whether it can become non-decreasing by modifying at most one element. A non-decreasing array means every element is less than or equal to the next element. The official statement defines this condition as nums[i] <= nums[i + 1] for every valid index i.

Return True if this is possible.

Otherwise, return False.

Input and Output

Example function shape:

def checkPossibility(nums: list[int]) -> bool:
    ...

Examples

Consider:

nums = [4, 2, 3]

This can become non-decreasing by changing 4 to a smaller value:

[1, 2, 3]

So the answer is:

True

Now consider:

nums = [4, 2, 1]

There are two drops:

4 > 2
2 > 1

One modification cannot fix both problems.

So the answer is:

False

Another important example:

nums = [3, 4, 2, 3]

There is a violation:

4 > 2

If we lower 4 to 2, the array becomes:

[3, 2, 2, 3]

This creates a new violation:

3 > 2

If we raise 2 to 4, the array becomes:

[3, 4, 4, 3]

This still has:

4 > 3

So the answer is:

False

First Thought: Count Violations

The array is invalid wherever:

nums[i] > nums[i + 1]

If this happens more than once, we should return False.

But counting violations alone is not enough.

For example:

[3, 4, 2, 3]

has only one visible violation:

4 > 2

but it still cannot be fixed with one modification.

So when we see a violation, we must decide whether it can be repaired safely.

Key Insight

Suppose we find:

nums[i] > nums[i + 1]

There are two possible ways to fix this local problem.

We can lower the left value:

nums[i] = nums[i + 1]

or raise the right value:

nums[i + 1] = nums[i]

The safer choice depends on the previous element.

If i == 0, there is no previous element, so lowering nums[i] is safe.

Otherwise, if:

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

then lowering nums[i] is safe, because it keeps the relation with the previous element valid.

If that condition is false, lowering nums[i] would create:

nums[i - 1] > nums[i]

So we must raise nums[i + 1] instead.

Algorithm

Scan the array from left to right.

Keep a counter called changes.

For each index i from 0 to n - 2:

1. If nums[i] <= nums[i + 1], continue.
2. Otherwise, we found a violation.
3. Increase changes.
4. If changes > 1, return False.
5. If i == 0 or nums[i - 1] <= nums[i + 1], lower nums[i].
6. Otherwise, raise nums[i + 1].

If the scan finishes, return True.

Correctness

The algorithm scans every adjacent pair.

Whenever it finds a violation nums[i] > nums[i + 1], at least one of those two elements must be modified. No other element can directly fix this adjacent inversion.

If this happens more than once, then at least two modifications are needed, so returning False is correct.

For the first violation, the algorithm chooses a modification that preserves the already-scanned prefix.

If lowering nums[i] is safe, it does so. This is safe when i == 0 or when nums[i - 1] <= nums[i + 1].

If lowering nums[i] is not safe, then raising nums[i + 1] is the only possible local repair that does not break the prefix before i.

After this repair, the scan continues. Since the algorithm allows only one repair and immediately rejects a second violation, it returns True exactly when the array can be made non-decreasing with at most one modification.

Complexity

Implementation

from typing import List

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        changes = 0

        for i in range(len(nums) - 1):
            if nums[i] <= nums[i + 1]:
                continue

            changes += 1

            if changes > 1:
                return False

            if i == 0 or nums[i - 1] <= nums[i + 1]:
                nums[i] = nums[i + 1]
            else:
                nums[i + 1] = nums[i]

        return True

Code Explanation

We count how many fixes are needed:

changes = 0

Then we scan adjacent pairs:

for i in range(len(nums) - 1):

If the pair is already valid, we do nothing:

if nums[i] <= nums[i + 1]:
    continue

If the pair is invalid, we need one modification:

changes += 1

More than one modification is not allowed:

if changes > 1:
    return False

Now we choose how to repair the current violation.

If we are at the beginning, or if the previous element can still fit before nums[i + 1], we lower nums[i]:

if i == 0 or nums[i - 1] <= nums[i + 1]:
    nums[i] = nums[i + 1]

Otherwise, lowering nums[i] would break the previous pair, so we raise nums[i + 1]:

else:
    nums[i + 1] = nums[i]

If the scan finishes, the array can be fixed with at most one change:

return True

Testing

def run_tests():
    s = Solution()

    assert s.checkPossibility([4, 2, 3]) is True
    assert s.checkPossibility([4, 2, 1]) is False
    assert s.checkPossibility([3, 4, 2, 3]) is False
    assert s.checkPossibility([1, 2, 3]) is True
    assert s.checkPossibility([1]) is True
    assert s.checkPossibility([2, 3, 3, 2, 4]) is True
    assert s.checkPossibility([1, 4, 1, 2]) is True
    assert s.checkPossibility([5, 7, 1, 8]) is True

    print("all tests passed")

run_tests()

Test meaning: