algoadvance

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

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 modifying at most one element.

Example 3:

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

Clarifying Questions

  1. Can the array be empty?
    • Generally, the array has at least one element as per such problems.
  2. What should we return for an already non-decreasing array?
    • We should return true since no modification is needed.
  3. Should the solution handle large input sizes effectively?
    • Yes, the solution should be optimized for larger input sizes.

Strategy

  1. Identify violations: Traverse through the list and check for any positions where nums[i] > nums[i + 1].
  2. Modification analysis: If more than one violation is found, return false. If exactly one violation is found:
    • Check if modifying nums[i] to nums[i + 1] or modifying nums[i + 1] to nums[i] results in a non-decreasing array.
  3. Boundary cases:
    • Ensure that we consider boundary indexes correctly to avoid out-of-bound errors.
    • Ensure that changing one element doesn’t violate any non-decreasing subarray property.

Code

def checkPossibility(nums):
    n = len(nums)
    if n <= 1:
        return True
    
    count = 0  # Count of modifications needed
    for i in range(n - 1):
        if nums[i] > nums[i + 1]:
            if count == 1:
                return False
            count += 1
            # Deciding whether to change nums[i] or nums[i + 1]
            if i == 0 or nums[i - 1] <= nums[i + 1]:
                nums[i] = nums[i + 1]  # Modify nums[i]
            else:
                nums[i + 1] = nums[i]  # Modify nums[i + 1]
    
    return True

# Example usage:
nums = [4, 2, 3]
print(checkPossibility(nums))  # Output: True

Time Complexity

The time complexity for this approach is O(n), where n is the length of the array. This is because we only traverse the array once to check for violations and possible fixes.

Space Complexity

The space complexity is O(1) since we only use a few auxiliary variables (count) and modify the array in-place without requiring extra space.

Try our interview co-pilot at AlgoAdvance.com