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