Code Implementation

class Solution:
    def checkPossibility(self, nums):
        modified = 0
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                if modified == 1:
                    return False
                modified += 1
                if i == 1 or nums[i] >= nums[i - 2]:
                    nums[i - 1] = nums[i]
                else:
                    nums[i] = nums[i - 1]
        return True
      

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int modified = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[i - 1]) {
                if (modified == 1)
                    return false;
                modified++;
                if (i == 1 || nums[i] >= nums[i - 2])
                    nums[i - 1] = nums[i];
                else
                    nums[i] = nums[i - 1];
            }
        }
        return true;
    }
};
      

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

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

Problem Description

You are given an array of integers nums. Your task is to determine if it is possible to make the entire array non-decreasing by modifying at most one element. An array is non-decreasing if for every index i (where 1 ≤ i < nums.length), nums[i - 1] ≤ nums[i] holds true.

You may change at most one element in nums to any value you want. The goal is to check if, after at most one such modification, the array becomes non-decreasing.

Constraints:

• There is at most one valid modification allowed.
• Do not remove or reorder elements; only modify a value.
• Array length: 1 ≤ nums.length ≤ 104
• Element values: -105 ≤ nums[i] ≤ 105

Thought Process

The main challenge is to detect whether the array can be made non-decreasing by changing only one element. At first glance, you might consider checking all possible single-element modifications, but that would be inefficient for large arrays.

Instead, let's look for places where the non-decreasing property is violated: whenever nums[i] < nums[i - 1]. If this happens more than once, more than one change would be needed, so we can return false right away.

If there's only one such violation, we need to check if changing either nums[i - 1] or nums[i] can fix the problem without introducing new violations elsewhere. This requires careful handling of edge cases, especially at the start of the array.

The optimized approach is to scan the array once, count violations, and, for each violation, see if a single fix is possible.

Solution Approach

• Step 1: Initialize a counter modified to zero. This will track how many times we need to modify an element.
• Step 2: Iterate through the array from the second element to the end.
  • For each position i, check if nums[i] < nums[i - 1]. If not, continue.
  • If this condition is true, increment modified. If modified becomes greater than 1, return false immediately.
  • To fix the violation, you have two options: modify nums[i - 1] or nums[i].
    • If i == 1 (violation at the start) or nums[i] >= nums[i - 2], set nums[i - 1] = nums[i]. This works because it does not affect earlier elements.
    • Otherwise, set nums[i] = nums[i - 1]. This is the only way to avoid creating a new violation.
• Step 3: If you finish scanning the array without needing more than one modification, return true.

This approach ensures we only ever need to fix a violation once, and we choose the fix that is least likely to cause further problems.

Example Walkthrough

Let's trace the solution for the input nums = [4, 2, 3]:

• Start with modified = 0.
• At i = 1:
  • nums[1] = 2, nums[0] = 4
  • Since 2 < 4, this is a violation.
  • modified becomes 1.
  • Since i == 1, we set nums[0] = 2 (so the array becomes [2, 2, 3]).
• At i = 2:
  • nums[2] = 3, nums[1] = 2
  • 3 ≥ 2, so no violation.
• We have only one modification, so we return true.

Another example: nums = [4, 2, 1]:

• At i = 1: 2 < 4 → modified = 1
• At i = 2: 1 < 2 → modified = 2
• Since we needed more than one modification, we return false.

Time and Space Complexity

• Brute-force approach: Try all possible single-element modifications and check if the array becomes non-decreasing. For each element, set it to every possible value (infeasible for large arrays). This would be O(n^2) or worse.
• Optimized approach (as implemented above):
  • Time Complexity: O(n), where n is the length of the array. We scan through the array once.
  • Space Complexity: O(1) extra space. We only use a few variables, and modifications are done in-place.

Summary

The key insight is that we only need to check for at most one violation of the non-decreasing property. If there is more than one, it's impossible to fix with a single change. For each violation, we check if modifying one of the two involved elements can resolve the issue without creating new problems. This greedy, single-pass solution is both efficient and elegant, avoiding the need for brute-force checks and minimizing complexity.