Python, Straightforward with Explanation


  • 2

    Call the array A good if it is monotone increasing.

    If there is more than one index for which A[i] > A[i+1], then more than one element of the array must be changed for A to be good. If there is no index for which A[i] > A[i+1], then the array is already good.

    Otherwise, let p be the problem index for which A[p] > A[p+1]. There are a few cases.

    • If p = 0, then we could make the array good by setting A[p] = A[p+1].
    • If p = len(A) - 2, then we could make the array good by setting A[p+1] = A[p].
    • Otherwise, A[p-1], A[p], A[p+1], A[p+2] all exist, and:
      • We could change A[p] to be between A[p-1] and A[p+1] if possible, or;
      • We could change A[p+1] to be between A[p] and A[p+2] if possible.
    def checkPossibility(self, A):
        p = None
        for i in xrange(len(A) - 1):
            if A[i] > A[i+1]:
                if p is not None:
                    return False
                p = i
    
        return (p is None or p == 0 or p == len(A)-2 or 
                A[p-1] <= A[p+1] or A[p] <= A[p+2])
    

  • 0
    1

    same to you O(N)
    '''
    class Solution:
    def checkPossibility(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    A=sorted(nums)
    p=len(nums)-1
    for i in range(len(nums)):
    if A[i]!=nums[i]:
    p=i
    break
    q=0
    for i in range(len(nums)-1,-1,-1):
    if A[i]!=nums[i]:
    q=i
    break
    return True if A[p:q]==nums[p+1:q+1] or A[p+1:q+1]==nums[p:q] else False
    '''


  • 0
    B

    @awice Thank you for your solution. I had one quick question:

    Why do we have to check elements at i-1 and i+1 as well as at i-2 and i? Wouldn't those at i-2 and i be checked in the previous iteration (i-1)?


  • 0
    S

    @BatCoder

    I think its how you must resolve violation.

    When nums[i] > nums[i+1], then either index i needs to be updated or index i+1 needs to be updated

    Case when index i must be updated = nums[i-1] <= nums[i+1] ( in which case nums[i] = nums[i-1] or nums[i] = nums[i+1] )
    Case when index i+1 must be updated = nums[i] <= nums[i+2] ( in which case nums[i+1] = nums[i] or nums[i+1] = nums[i+2])

    Corner cases -
    when index i = 0, i-1 comparison is out of question, so nums[0] = nums[1] - is how you need to resolve violation
    when index i = n-1, i+1 comparison is out of question, so nums[n-1] = nums[n-2] is how you resolve violation

    Whenever you resolve violation only smaller number must replace higher number to avoid cascading violation to further indices.

    Thanks @awice i could not solve this, i got stuck to "p is not None" case.


Log in to reply
 

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