Leetcode: Non-decreasing Array

Modify one element to make array non-decreasing

Similar Problems:

Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.

We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).

Example 1:

Input: [4,2,3]
Output: True

Explanation: You could modify the first 
 to get a non-decreasing array.

Example 2:

Input: [4,2,1]
Output: False

Explanation: You can’t get a non-decreasing array by modify at most one element.
Note: The n belongs to [1, 10,000].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/non-decreasing-array
## Basic Ideas: If we have two decreasing couples, we can't fix it with one change. Right?
## Complexity: Time O(n), Space O(1)
##  1     4         2       3
##      index1   index2
class Solution(object):
    def checkPossibility(self, nums):
        :type nums: List[int]
        :rtype: bool
        index1 = None
        index2 = None
        length = len(nums)
        for i in range(0, length - 1):
            if nums[i] > nums[i+1]:
                if index1 is not None:
                    # already one decreasing
                    return False
                index1 = i
                index2 = i+1

        # print("index1: %d, index2: %d" % (index1, index2))
        if index1 is None:
            # no decreasing 
            return True

        ret = False
        if index2 == length -1:
            # last item
            ret = True
        elif index1 == 0:
            # first item
            ret = True
            #                 index1
            #                                   (index2+1)
            #   (index1-1)          
            #                          index2       
            if nums[index1] <= nums[index2+1]:
                # only change index2
                ret = True
            if nums[index2] >= nums[index1-1]:
                # only change index1
                ret = True
        return ret

if __name__ == '__main__':
    s = Solution()
    print s.checkPossibility([4,2,3])
    print s.checkPossibility([4,2,1])
    print s.checkPossibility([4])

Share It, If You Like It.

Leave a Reply

Your email address will not be published.