Shortest Unsorted Continuous Subarray in O(N) Time

Problem Statement

Return the shortest such subarray and output its length.

Key Ideas

  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

Space Complexity

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Felix Lee

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.