Self explanatory O(n) solution in Python


#1

class Solution:
# @param A : list of integers
# @return a list of integers
def subUnsort(self, A):
l = len(A)
st = 0
end = l - 1
is_unsorted = False

    for i in range(1, l):
        if A[i] != A[i - 1] and A[i] < A[i - 1]:
            is_unsorted = True
            st = i - 1
            break

    for i in range(l - 1, 0, -1):
        if A[i] != A[i - 1] and A[i] < A[i - 1]:
            end = i
            break

    if not is_unsorted:
        return [-1]

    mn = min(A[st:end + 1])
    mx = max(A[st:end + 1])

    for i in range(st):
        if A[i] > mn:
            st = i
            break

    for i in range(l - 1, end, -1):
        if A[i] < mx:
            end = i
            break

    return [st, end]