Shortest Unsorted Continuous Subarray - Solution & Explanation

Problem Overview: You receive an integer array and need the length of the shortest continuous subarray that must be sorted so the entire array becomes sorted in non‑decreasing order. If the array is already sorted, return 0.

Approach 1: Using Sorting to Identify Subarray (Time: O(n log n), Space: O(n))

Create a sorted copy of the array and compare it with the original. The first index from the left where elements differ marks the start of the unsorted region. The first index from the right where they differ marks the end. The subarray between these two indices is the smallest segment that must be sorted to make the entire array ordered. This approach relies on standard sorting and straightforward iteration, which makes it easy to reason about and implement. It works well when clarity matters more than strict optimal complexity.

Implementation steps are simple: copy the array, sort the copy, scan from the left until values mismatch, then scan from the right. If no mismatch appears, the array was already sorted. The distance between the two mismatches plus one gives the result.

Approach 2: Single Pass Scan for Minimum and Maximum Deviations (Time: O(n), Space: O(1))

The optimal solution avoids sorting and instead detects where ordering breaks. Traverse from left to right while tracking the maximum value seen so far. When the current element is smaller than that maximum, the array is out of order and the right boundary of the unsorted region must expand. Then traverse from right to left while tracking the minimum value seen so far. If the current element is larger than that minimum, update the left boundary.

The key insight: any element that violates the running max or running min indicates that earlier or later elements must be included in the subarray. This greedy scanning technique finds the exact boundaries without extra storage. The logic fits naturally with array traversal patterns and is often discussed alongside two pointers style bidirectional scans.

This approach is preferred when performance matters. Only two linear scans are required, and no auxiliary arrays are allocated.

Alternative Insight: Monotonic Stack

A related method uses a monotonic stack to detect the first violations of sorted order from both directions. A decreasing stack from the left identifies the earliest index where order breaks, while an increasing stack from the right finds the final boundary. Time complexity remains O(n) with O(n) stack space. It is useful if you already recognize monotonic stack patterns in array ordering problems.

Recommended for interviews: Start with the sorting comparison because it proves you understand the goal of locating mismatched boundaries. Then present the linear scan solution. Interviewers typically expect the O(n) greedy scan because it shows you can reason about order violations without relying on sorting.