665 - Non-decreasing Array

Difficulty: Medium | Pattern: Greedy | Company tags: Google, Amazon, Facebook

Problem Statement

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

We define an array as non-decreasing if nums[i] <= nums[i+1] for every i (0-indexed) where 0 <= i <= n-2.

Example 1:

Input: nums = [4,2,3]
Output: true  (change 4 to 2 or less)

Example 2:

Input: nums = [4,2,1]
Output: false  (two violations)

Solution: Greedy — O(n), O(1)

Key insight: When violation found at nums[i] > nums[i+1]:

• If i == 0 or nums[i-1] <= nums[i+1]: lower nums[i] to nums[i+1] (safe)
• Otherwise: raise nums[i+1] to nums[i]

Track count of fixes; if more than 1, return False.

def checkPossibility(nums: list[int]) -> bool:
    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]
            else:
                nums[i] = nums[i+1]
    
    return True

Dry Run

nums = [3,4,2,3]

i	nums[i]	nums[i+1]	violation?	action
0	3	4	No	—
1	4	2	Yes (count=1)	nums[0]=3 gt 2, raise nums[2]=4 → [3,4,4,3]
2	4	3	Yes (count=2)	return False

Result: False ✓

nums = [4,2,3]

i	nums[i]	nums[i+1]	violation?	action
0	4	2	Yes (count=1)	i=0, lower nums[0]=2 → [2,2,3]
1	2	3	No	—

Result: True ✓

Edge Cases

• Empty or single element → always True
• Violation at first position → always lower first element
• Violation at last position → always lower last element

Complexity

• Time: O(n)
• Space: O(1)