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]

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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).