Non-decreasing Array: One Modification Check

May 21, 20265 min read

leetcodeproblemmediumarrays

LeetCode Non-decreasing Array (problem 665) gives you an integer array nums with n elements. You need to decide whether you can make the array non-decreasing by modifying at most one element. An array is non-decreasing when every element is greater than or equal to the one before it.

Given nums = [4, 2, 3], the answer is true. You can set nums[0] = 2 to get [2, 2, 3], which is non-decreasing. But for nums = [4, 2, 1], the answer is false because no single change can fix both violations.

The pair (4, 2) at indices 0-1 violates non-decreasing order. Lowering nums[0] to 2 fixes it in one modification.

Approach

The idea is to scan left to right and count how many times nums[i] is greater than nums[i + 1]. Each such pair is a "violation" of the non-decreasing property.

If you find zero violations, the array is already non-decreasing. Return true.
If you find two or more violations, a single modification cannot fix the array. Return false.
If you find exactly one violation at index i, you have two choices: lower nums[i] down to nums[i + 1], or raise nums[i + 1] up to nums[i]. You need to check whether either option keeps the rest of the array valid.

The trick is deciding which fix to apply. When i is 0 or nums[i - 1] is at most nums[i + 1], you can safely lower nums[i]. Otherwise, you raise nums[i + 1] to match nums[i] and check that it does not break the relationship with nums[i + 2].

Practice this problem with spaced repetition

The Python solution

def checkPossibility(nums):
    count = 0
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            count += 1
            if count > 1:
                return False
            if i > 0 and nums[i - 1] > nums[i + 1]:
                nums[i + 1] = nums[i]
    return True

We iterate through pairs of adjacent elements looking for violations where nums[i] exceeds nums[i + 1].
The variable count tracks how many violations we have seen. If it ever exceeds 1, we return False immediately.
When we find the first violation, we decide how to fix it. If i is 0, there is no left neighbor to worry about, so lowering nums[i] always works (we do not even need to modify the array explicitly). If nums[i - 1] is greater than nums[i + 1], lowering nums[i] would break the pair at i - 1 and i, so instead we raise nums[i + 1] to nums[i].
After the loop, if we never exceeded one violation, the answer is True.

The key insight is that you do not need to try both fixes and simulate the full array twice. By choosing the right fix greedily at the violation point, you maintain the best chance for the rest of the array to remain valid. If nums[i - 1] already fits under nums[i + 1], lowering nums[i] is always the safer choice because it keeps the values small. Only when the left neighbor forces you do you raise nums[i + 1] instead.

Drill array scanning patterns with spaced repetition

Visual walkthrough

Step 1: Scan left to right for violations

Compare each pair nums[i] and nums[i+1]. Mark any pair where nums[i] is greater than nums[i+1].

Step 2: Count the violations

We found exactly 1 violation. If there were 2 or more, we would immediately return false.

Step 3a: Option A -- lower nums[i]

Set nums[0] = nums[1] = 2. Check if the array is now non-decreasing: [2, 2, 3]. It works.

Step 3b: Option B -- raise nums[i+1]

Set nums[1] = nums[0] = 4. Check the result: [4, 4, 3]. That creates a new violation at index 1-2, so this fix would not work here.

Step 4: The decision at the violation point

Case: i=0 or nums[i-1] fits

Case: nums[i-1] too large

When nums[i] is greater than nums[i+1], compare with the neighbor before i. If i is 0 or nums[i-1] is at most nums[i+1], lower nums[i]. Otherwise, raise nums[i+1].

The walkthrough shows how you examine the violation at index 0-1 in [4, 2, 3]. Since i is 0, there is no left neighbor constraint, so lowering nums[0] is the natural fix. In a case like [3, 4, 2, 3], the violation is at index 1-2. Here nums[0] = 3 is greater than nums[2] = 2, so lowering nums[1] would leave [3, 2, ...] which is still broken. Instead, you raise nums[2] to 4, giving [3, 4, 4, 3], but that creates yet another violation. Two violations means false.

Complexity analysis

Metric	Value	Why
Time	O(n)	Single pass through the array
Space	O(1)	Only a counter and index variables

You visit each element once. The fix is applied in-place with no extra data structures. This is optimal since you must read every element at least once to verify the non-decreasing property.

Building blocks

This problem relies on a single-pass greedy scan. The same pattern appears in many array problems where you need to verify or maintain a property while allowing a limited number of exceptions:

Gas Station (LeetCode 134) scans circularly and resets when a constraint fails, similar to counting violations and bailing early.
Jump Game (LeetCode 55) tracks a running "reach" value in a single pass, deciding greedily at each step.
Best Time to Buy and Sell Stock (LeetCode 121) maintains a running minimum in one sweep, much like tracking violation count here.

The mental model: walk through the array, track a small amount of state (here, a violation count), and make a local greedy decision whenever you encounter a problem.

Edge cases

Already non-decreasing (e.g., [1, 2, 3]): zero violations, return true immediately.
Single element or two elements: always true since you can fix any pair with one change.
Violation at the very end (e.g., [1, 2, 5, 3]): one violation at index 2-3. Since nums[1] = 2 fits under nums[3] = 3, lowering nums[2] works.
Violation at the very start (e.g., [4, 2, 3]): i is 0, so there is no left neighbor. Lowering nums[0] is always safe.
All equal values (e.g., [5, 5, 5]): non-decreasing by definition, zero violations.
Descending array (e.g., [5, 4, 3, 2]): multiple violations, return false after the second one.

From understanding to recall

The logic behind this problem is compact, but the two-case decision at the violation point is easy to get wrong under pressure. You might forget to check the left neighbor, or you might mix up which element to modify. The best way to lock it in is to practice writing the solution from scratch a few times, then space out your reviews. Focus on the decision point: "Is i zero or does the left neighbor fit? If yes, lower. Otherwise, raise." Once that conditional is automatic, the rest of the solution flows naturally.

Best Time to Buy and Sell Stock - Another single-pass array scan
Move Zeroes - Array modification with a single pass
Remove Duplicates from Sorted Array - In-place array modification

Try CodeBricks free