Problem Description

You are given an array nums containing n integers. Your task is to determine whether this array can be made non-decreasing by modifying at most one element.

An array is considered non-decreasing if each element is less than or equal to the next element. Formally, nums[i] <= nums[i + 1] must hold for all valid indices i where 0 <= i <= n - 2.

The key points to understand:

• You can modify at most one element (change its value to any number)
• You can also choose to modify zero elements if the array is already non-decreasing
• After the modification (if any), the entire array should satisfy the non-decreasing property
• Return true if it's possible to achieve a non-decreasing array with at most one modification, otherwise return false

For example:

• [4, 2, 3] → Can become [1, 2, 3] or [4, 4, 4] by changing one element, so return true
• [4, 2, 1] → Cannot become non-decreasing by changing just one element, so return false
• [1, 2, 3] → Already non-decreasing, so return true

Intuition

When we scan through the array, we're looking for positions where the non-decreasing property is violated - that is, where nums[i] > nums[i + 1]. If we find more than one such violation, it's impossible to fix the array with just one modification.

The key insight is that when we find a violation at position i (where nums[i] > nums[i + 1]), we have two choices to fix it:

1. Lower nums[i] to match nums[i + 1] - This makes the current pair valid without affecting future comparisons
2. Raise nums[i + 1] to match nums[i] - This fixes the current pair but might create issues with nums[i + 1] and nums[i + 2]

Why do we need to try both options? Consider these examples:

• [3, 4, 2, 5]: At the violation (4 > 2), if we raise 2 to 4, we get [3, 4, 4, 5] ✓
• [1, 4, 2, 3]: At the violation (4 > 2), raising 2 to 4 gives [1, 4, 4, 3] which is still invalid. But lowering 4 to 2 gives [1, 2, 2, 3] ✓

The strategy is straightforward: iterate through the array until we find the first violation. When found, try both possible fixes and check if either results in a valid non-decreasing array. If we never find a violation, the array is already non-decreasing.

This approach works because if there's exactly one violation, one of these two modifications must work if a solution exists. If neither works, or if we find multiple violations, then it's impossible to fix the array with just one change.

Solution Approach

The implementation follows a clean and efficient approach:

1. Helper Function for Validation: First, we define an is_sorted helper function that checks if an array is non-decreasing. It uses Python's pairwise function to iterate through consecutive pairs and verifies that each pair satisfies a <= b.

2. Main Algorithm:

   • Iterate through the array from index 0 to n-2, checking each consecutive pair (nums[i], nums[i+1])

   • When we find the first violation where nums[i] > nums[i+1]:

     Try Option 1: Lower nums[i] to match nums[i+1]

     nums[i] = b  # where b = nums[i+1]

     • Check if the entire array is now sorted using is_sorted(nums)
     • If yes, return True

     Try Option 2: If Option 1 didn't work, raise nums[i+1] to match nums[i]

     nums[i] = nums[i + 1] = a  # where a = original nums[i]

     • This effectively restores nums[i] to its original value and sets nums[i+1] equal to it
     • Check if the array is now sorted and return the result

3. No Violation Found: If we complete the loop without finding any violation, the array is already non-decreasing, so return True

Time Complexity: O(n) - We iterate through the array at most twice (once in the main loop and once in is_sorted)

Space Complexity: O(1) - We only use a constant amount of extra space (modifying the array in-place)

The elegance of this solution lies in its simplicity - it directly tries both possible fixes when encountering a violation and immediately checks if either works, avoiding complex edge case handling.

Example Walkthrough

Let's walk through the array [3, 4, 2, 5] to demonstrate the solution approach.

Step 1: Initial scan for violations

• Compare pairs: (3,4) ✓, (4,2) ✗, (2,5) ✓
• Found violation at index 1: nums[1] = 4 > nums[2] = 2

Step 2: Try Option 1 - Lower nums[1] to match nums[2]

• Set nums[1] = 2, array becomes [3, 2, 2, 5]
• Check if sorted: (3,2) ✗ - Not sorted!
• This option doesn't work

Step 3: Try Option 2 - Raise nums[2] to match nums[1]

• Restore nums[1] = 4 and set nums[2] = 4
• Array becomes [3, 4, 4, 5]
• Check if sorted: (3,4) ✓, (4,4) ✓, (4,5) ✓ - Sorted!
• Return True

Let's trace through another example: [1, 4, 2, 3]

Step 1: Initial scan

• Compare pairs: (1,4) ✓, (4,2) ✗, (2,3) ✓
• Found violation at index 1: nums[1] = 4 > nums[2] = 2

Step 2: Try Option 1 - Lower nums[1]

• Set nums[1] = 2, array becomes [1, 2, 2, 3]
• Check if sorted: (1,2) ✓, (2,2) ✓, (2,3) ✓ - Sorted!
• Return True

For an already sorted array like [1, 2, 3, 4]:

• Compare all pairs: (1,2) ✓, (2,3) ✓, (3,4) ✓
• No violations found
• Return True immediately

This approach efficiently handles all cases by trying both modification strategies only when needed.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array once with the main loop from i = 0 to n - 2, which takes O(n) time. When a violation is found (where nums[i] > nums[i + 1]), the algorithm performs at most two checks using the is_sorted function. Each call to is_sorted uses the pairwise function which iterates through the array once, taking O(n) time. Since we encounter at most one violation (if more than one exists, we return False), the is_sorted function is called at most twice. Therefore, the overall time complexity is O(n) + 2 * O(n) = O(n).

Space Complexity: O(1)

The algorithm modifies the input array in-place and only uses a constant amount of extra space for variables like i, a, b, and n. The pairwise function in Python creates an iterator that doesn't store the entire paired sequence in memory, using only O(1) additional space. The all() function with a generator expression also operates with O(1) space as it evaluates lazily. Therefore, the total space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Array

The most critical pitfall in this solution is that it modifies the input array in-place. This can be problematic because:

• The caller might not expect their data to be mutated
• If the function is called multiple times with the same array, subsequent calls will operate on already-modified data
• It violates the principle of avoiding side effects in functions

Example of the problem:

nums = [4, 2, 3]
solution = Solution()
result1 = solution.checkPossibility(nums)  # Returns True
print(nums)  # Array has been modified! Could be [2, 2, 3] or [4, 4, 3]
result2 = solution.checkPossibility(nums)  # Operates on modified array

2. Missing Import Statement

The pairwise function from itertools is used inside a nested function, but the import happens within that function. This can cause:

• Import errors if not handled properly
• Performance issues if the function is called repeatedly (though Python caches imports)

Solution to Fix These Pitfalls

from itertools import pairwise
from typing import List

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        """
        Check if array can become non-decreasing by modifying at most one element.
      
        Args:
            nums: List of integers to check
          
        Returns:
            True if array can be made non-decreasing with at most one modification
        """
      
        def is_non_decreasing(arr: List[int]) -> bool:
            """Check if array is non-decreasing."""
            return all(a <= b for a, b in pairwise(arr))
      
        n = len(nums)
      
        # Find the first violation
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                # Create copies to avoid modifying original array
                # Strategy 1: Try lowering nums[i]
                test_array1 = nums.copy()
                test_array1[i] = nums[i + 1]
                if is_non_decreasing(test_array1):
                    return True
              
                # Strategy 2: Try raising nums[i+1]
                test_array2 = nums.copy()
                test_array2[i + 1] = nums[i]
                return is_non_decreasing(test_array2)
      
        # No violations found
        return True

Alternative Space-Efficient Solution Without Copying: If you want to avoid creating copies but still not modify the original array, you can check the conditions without actually modifying any array:

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        n = len(nums)
        violation_count = 0
      
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                violation_count += 1
              
                if violation_count > 1:
                    return False
              
                # Check if modifying nums[i] or nums[i+1] would work
                # without actually modifying the array
                if i > 0 and nums[i - 1] > nums[i + 1]:
                    # Can't lower nums[i] to nums[i+1] because it would violate
                    # the relationship with nums[i-1]
                    if i + 2 < n and nums[i] > nums[i + 2]:
                        # Can't raise nums[i+1] to nums[i] either
                        return False
      
        return True

This alternative approach counts violations and checks feasibility without creating copies or modifying the original array, making it both space-efficient and side-effect free.