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.
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 (:
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
@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
@xiaoyudeng666 That's brilliant! Changed the code to incorporate your suggestion (:
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
@zjlvmiao simple and good solution!
May I ask you why do you use one = nums[:] instead of one = nums? What is the difference between the two? Thank you!
That was making a copy of
num, otherwise they will refer to the same array
@user1749 Because I will be modifying both
two and don't want to be mutating the same array, hence I make two copies first and operate on the copies instead.
@zjlvmiao Good idea!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.