# Shortest Unsorted Continuous Subarray in O(N) Time

# Problem Statement

Given an integer array `nums`

, you need to find one **continuous subarray** that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return *the shortest such subarray and output its length*.

# Key Ideas

Consider the case `nums = [1, 5, 2, -1, 7]`

- Find the first element that is out of order from the left.
`5`

is the one out of order because it is larger than`2`

. The number should keep increasing as we move to the right. - Find the last element that is out of order from the right.
`-1`

is the one out of order because it is smaller than`2`

. The number should keep decreasing as we move to the left. - After Step 1 and 2, we will get the
**initial window/subarray**(`[5, 2, -1]`

). However, we will not get a sorted array by just sorting this 3 elements. We need to include the first element,`1`

as well.`[-1, 1, 2, 5, 7]`

is the correct sorted array. - So we need to expand our window to the left to include more elements if our
**initial subarray contains a number that is smaller than the number outside the window on the left**. For example, we need to include`1`

at index 0 because it is larger than`-1`

which exists in our initial window. - Do the same for the right side. If the initial subarray contains a number that is larger than the number outside the window on the right.
- For this example,
`[1, 5, 2, -1] => Length = 4`

is the correct answer to our problem

# Time and Space Complexity

## Time Complexity

We look through the array only once, so the algorithm is *O(N).*

## Space Complexity

The algorithm runs in constant space *O(1).*