python one pass solution


  • 0
    Z

    When we found the number in descending order there are three conditions we need to check:
    Take this list as a negative example:
    [3, 4, 2, 3]

    1. We haven't modify any number yet
    2. Number 2 at index 2 must not smaller than number 3 at index 0 (meaning we must modify number 2 at index 2 to be at least 4)
    3. At the same time number 4 at index 1 must not bigger than 3 at index 3 (meaning we must modify 4 at index 1 to be at most 2)

    Now we know we must modify at least twice to satisfy both conditions.

    def checkPossibility(self, nums):
        modified = False
        prev = -float('inf')
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                if modified or nums[i] < prev and i < len(nums) - 1 and nums[i - 1] > nums[i + 1]:
                    return False
                modified = True
            prev = nums[i - 1]
        return True

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.