Python O(N) solution with explaination

  • -1

    Find all continuous reverse pair.
    The minimum of pair[1] is the minimum of sorted list and the maximum of pair[0] is the maximum of sorted list.

    def findUnsortedSubarray(self, l):
            reverse = filter(lambda p: p[0] > p[1], zip(l, l[1:]))
            if not reverse: return 0
            left, right = min(p[1] for p in reverse), max(p[0] for p in reverse)
            for i in xrange(len(l)):
                if l[i] > left: break
            for j in xrange(len(l)):
                if l[-j-1] < right: break
            return len(l) - j - i

Log in to reply

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