Back to solutions

Non Decreasing Array

MediumArrays

Can the array become non-decreasing by changing at most one element?

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

Greedy fix at each drop

Time O(n)Space O(1)

Scan for places where nums[i-1] > nums[i]. Count such drops; more than one means it is impossible. At the single drop, decide which element to change: lower nums[i-1] to nums[i] when safe (nums[i-2] <= nums[i]), otherwise raise nums[i] up to nums[i-1]. Picking the change that keeps the prefix valid maximises future success.

Key terms
non-decreasing:
Every element is less than or equal to the one after it.
drop:
An adjacent pair where the earlier value is greater than the later one.
bool checkPossibility(vector<int>& nums) {
    int changes = 0;
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i - 1] > nums[i]) {
            if (++changes > 1) return false;
            if (i < 2 || nums[i - 2] <= nums[i]) nums[i - 1] = nums[i];
            else nums[i] = nums[i - 1];
        }
    }
    return true;
}
Step by step
  1. Walk the array counting drops where nums[i-1] > nums[i].
  2. If a second drop occurs, return false.
  3. At the first drop, if nums[i-2] <= nums[i] (or i < 2), lower nums[i-1] to nums[i].
  4. Otherwise raise nums[i] to nums[i-1]. If at most one drop was fixed, return true.