# Python, Straightforward with Explanation

• 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])
``````

• 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
'''

• @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`)?

• @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.

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