Non-decreasing Array

medium array greedy

Problem

Given an array nums, return true if you can make it non-decreasing by modifying at most one element. At each violation nums[i] > nums[i+1], lower nums[i+1] to nums[i] if nums[i-1] ≤ nums[i+1]; otherwise raise nums[i] to nums[i+1].

Inputnums = [4, 2, 3]

Outputtrue

Lower nums[0]=4 to 2 (or any value ≤ 2), giving [2, 2, 3] which is non-decreasing.

nums (comma-separated)

def check_possibility(nums):
    fixes = 0
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            fixes += 1
            if fixes > 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

function checkPossibility(nums) {
  let fixes = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] > nums[i + 1]) {
      fixes++;
      if (fixes > 1) return false;
      if (i > 0 && nums[i - 1] > nums[i + 1]) nums[i + 1] = nums[i];
      else nums[i] = nums[i + 1];
    }
  }
  return true;
}

class Solution {
    public boolean checkPossibility(int[] nums) {
        int fixes = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                fixes++;
                if (fixes > 1) return false;
                if (i > 0 && nums[i - 1] > nums[i + 1]) nums[i + 1] = nums[i];
                else nums[i] = nums[i + 1];
            }
        }
        return true;
    }
}

bool checkPossibility(vector<int>& nums) {
    int fixes = 0;
    for (int i = 0; i < (int) nums.size() - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            fixes++;
            if (fixes > 1) return false;
            if (i > 0 && nums[i - 1] > nums[i + 1]) nums[i + 1] = nums[i];
            else nums[i] = nums[i + 1];
        }
    }
    return true;
}

Explanation

We are allowed one repair. The plan is to walk left to right, and the moment we see a spot where a number is bigger than the one after it (a violation, nums[i] > nums[i+1]), we fix it. If we ever need a second fix, the answer is false.

The clever part is how we fix it. When we hit a violation, we usually want to lower the bigger left value nums[i] down to nums[i+1], because making the left side smaller helps keep the rest sorted.

But that does not always work: if there is an even larger value two steps back (nums[i-1] > nums[i+1]), lowering nums[i] would create a new break with nums[i-1]. In that case we instead raise nums[i+1] up to nums[i].

Example: nums = [4, 2, 3]. At i=0 we see 4 > 2. There is nothing before index 0, so we lower nums[0] to 2, giving [2, 2, 3], which is sorted with just one fix, so we return true.

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