Non Decreasing Array - Leetcode Solution

The Non Decreasing Array problem on LeetCode asks us to determine whether we can make an array non-decreasing by modifying at most one element. A non-decreasing array is an array in which the elements are in non-decreasing order, i.e., each element is greater than or equal to the previous element.

To solve this problem, we can iterate over the array and check if any element is greater than the next element. If we find such an element, we can modify it to be equal to the next element. We can then check if the resulting array is non-decreasing.

If we encounter a second instance where an element is greater than the next element, we cannot make the array non-decreasing by modifying at most one element. In this case, we return false.

Here is the detailed solution in Python:

def checkPossibility(nums):
    modified = False  # a flag to track whether we have modified an element
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            if modified:
                return False  # we have already modified an element, cannot make array non-decreasing
            if i == 0 or nums[i-1] <= nums[i+1]:
                # can modify nums[i] to nums[i+1] to make the array non-decreasing
                nums[i] = nums[i+1]  
            else:
                # can modify nums[i+1] to nums[i] to make the array non-decreasing
                nums[i+1] = nums[i]  
            modified = True

    return True

The solution has a running time of O(n) and uses constant extra space.

1