Python, Straightforward with Explanation

  • 0

    Consider the sorted array, B = sorted(A). Recall that A is to be transformed into B. If A and B have the same first element, then without loss of generality we shouldn't have our swap involve those elements. Similarly, if A and B have the same last element, we can ignore them too. What remains is some interior A[i: j+1] that differs from the sorted array in the first and last position (at A[i] and A[j]). Those elements must be swapped, and so the length of the subarray is j+1-i.

    def findUnsortedSubarray(self, A):
        B = sorted(A)
        if A == B: return 0
        for i in xrange(len(A)):
            if A[i] != B[i]: break
        for j in xrange(len(A)-1, -1, -1):
            if A[j] != B[j]: break
        return j - i + 1

  • 0

    What's the run time for this code?

  • 0

    @k20052 We sort the array in N log N, then do a linear scan in N. The first term dominates the second one, so the final answer is O(N log N), where N is the length of the array.

Log in to reply

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