Problem

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 is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Examples

Example 1:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Example 2:

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

Solution

Method 1 - Greedy - Count Modifications and Modify Array

This question can be a little bit deceiving since it looks like you only need to look out for one discrepancy. But that is not correct. Lets look at example:

nums    = [4,4,3,2]
indices =  0 1 2 3

In the above array, we have a discrepancy and index i = 2. i.e for value 3. we have two choices that might fix the discrepancy:

  • set nums[i-1] = nums[i],  or 

  • set nums[i] = nums[i-1]. Both options would fix the discrepancy but only one of these changes is valid. How should we decide? Well, we’d need to make our decision based on the value at nums[i-2].

  • If the value at nums[i-2] is greater than nums[i], then we’d need to set nums[i] = nums[i-1] since that would change the smaller value to the larger one.

  • Else, we change the larger one to the smaller by setting nums[i-1] = nums[i].

Looking at above example:

As we have discrepancy at index i = 2, we check at i= 0; As nums[0] > nums[2], hence we set nums[2] = nums[1].

Now that we’ve dealt with our first discrepancy, we need to make sure we don’t encounter any more.

We’re only allowed to make at most one modification. So we can confidently return false if we find another discrepancy.

Code

Java
class Solution {

	public boolean checkPossibility(int[] nums) {
		for (int i = 1, modified = 0; i < nums.length; i++) {
			if (nums[i - 1] > nums[i]) {
				if (modified++ == 1) {
					return false;
				}

				if (i >= 2 && nums[i - 2] > nums[i]) {
					nums[i] = nums[i - 1];
				} else {
					nums[i - 1] = nums[i];
				}
			}
		}

		return true;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1), but array modification.

Method 2 - Without Modifying Array

Note: This can also be achieved without modifying the input array. We’ll keep track of the “previous” value using prev instead of directly accessing nums[i-1]. Therefore, instead of setting nums[i] = nums[i-1], we can avoid updating prev. In other words, we’re choosing whether we want prev to be our smaller or larger value at the discrepancy.

Code

Java
class Solution {

	public boolean checkPossibility(int[] nums) {
		for (int i = 1, modified = 0, prev = nums[0]; i < nums.length; i++) {
			if (nums[i]<prev) {
				if (modified++ == 1) {
					return false;
				}

				if (i >= 2 && nums[i - 2] > nums[i]) {
					continue;
				}
			}

			prev = nums[i];
		}

		return true;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)