Problem statement

https://leetcode.com/problems/non-decreasing-array/

Solution

What we need to check is the following: first, that we have only one pair of adjacent elements, such that first is more then the next one. If we found two such elements, we return False. If there is not such elements, we return True. Also we return True if this element is the first or the last. Finally, we return True if we can remove this element and have A[p-1] <= A[p+1] or remove next element and have A[p] <= A[p+2].

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def checkPossibility(self, A):
        p, n = -1, len(A)
        for i in range(n - 1):
            if A[i] > A[i+1]:
                if p != -1: return False
                p = i

        return p in [-1, 0, n-2] or A[p-1] <= A[p+1] or A[p] <= A[p+2]