# Python, Straightforward with Explanation

• 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
``````

• What's the run time for this code?

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

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