Python Extremely Easy to Understand


  • 10

    First, find a pair where the order is wrong. Then there are two possibilities, either the first in the pair can be modified or the second can be modified to create a valid sequence. We simply modify both of them and check for validity of the modified arrays by comparing with the array after sorting.

    I find this approach the easiest to reason about and understand.

    By Yang Shun

    class Solution(object):
        def checkPossibility(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            one, two = nums[:], nums[:]
            for i in range(len(nums) - 1):
                if nums[i] > nums[i + 1]:
                    one[i] = nums[i + 1]
                    two[i + 1] = nums[i]
                    break
            return one == sorted(one) or two == sorted(two)
    

    Thanks to @xiaoyudeng666 for the tip (:


  • 1
    B

    That was a great idea


  • 1

    Same idea but a little bit compact:

        def checkPossibility(self, nums):
            isND = lambda ns: all(map(operator.le, ns[:-1], ns[1:]))
            for i in range(1, len(nums)):
                if nums[i-1] > nums[i]:
                    return isND(nums[:i-1]+nums[i:]) or isND(nums[:i]+nums[i+1:])
            return True
    

  • 1
    X

    @yangshun great idea! But you don't need to define an extra inner function, you can return "one == sorted(one) or two == sorted(two)" instead


  • 0

    @xiaoyudeng666 That's brilliant! Changed the code to incorporate your suggestion (:


  • 0
    class Solution(object):
        def checkPossibility(self, nums):
        # greedy, find i with nums[i-1]>nums[i]
        # modify nums[i-1] or nums[i], e.g, [3,4,2,3]
            cnt = 0
            for i in range(1, len(nums)):
                if nums[i - 1] > nums[i]:
                    cnt += 1
                    if i < 2 or nums[i - 2] <= nums[i]:
                        nums[i - 1] = nums[i] # modify nums[i-1]
                    else:
                        nums[i] = nums[i - 1] # modify nums[i]
            return cnt <= 1
    

Log in to reply
 

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