Shortest Unsorted Continuous Subarray

Shortest Unsorted Continuous Subarray

What is this problem about?

The Shortest Unsorted Continuous Subarray interview question asks you to find the shortest subarray such that if you sort it, the entire array becomes sorted. Equivalently, find the smallest window [l, r] where sorting nums[l..r] results in the whole array being non-decreasing. Return r - l + 1, or 0 if the array is already sorted.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this problem because it has an elegant O(n) solution that avoids sorting. The sorted comparison approach is O(n log n); the O(n) approach finds the leftmost element that is out of position and the rightmost element that is out of position using a single forward and backward scan with running min/max. It tests candidates' ability to reduce an apparently sorting problem to a linear scan.

Algorithmic pattern used

The pattern is two-pass linear scan with running max/min. Forward pass: find the last index right where nums[i] < running_max_from_left. Backward pass: find the first index left where nums[i] > running_min_from_right. If no such index is found in either pass, the array is sorted (return 0). Otherwise, return right - left + 1. This is O(n) with O(1) space.

Example explanation

Array: [2, 6, 4, 8, 10, 9, 15].

Forward pass (running max from left):

• max=2. max=6. 4<6 → right=2. max=8. max=10. 9<10 → right=5. max=15.
• right = 5.

Backward pass (running min from right):

• min=15. min=9. min=8. 10>8 → left=4. min=4. min=4. 6>4 → left=1. min=2.
• left = 1.

Answer: right - left + 1 = 5 - 1 + 1 = 5 (subarray [6, 4, 8, 10, 9]).

Common mistakes candidates make

• Using sorted(nums) and comparing element by element — O(n log n) and uses extra space; the O(n) approach is expected.
• Finding only the first unsorted element without scanning for the full range — must find both left and right boundaries.
• Not accounting for elements outside the naive boundary that are still out of range — left and right may need to extend beyond the first and last unsorted elements.
• Returning right - left instead of right - left + 1 (off-by-one in subarray length).

Interview preparation tip

For the Shortest Unsorted Continuous Subarray coding problem, the two-pointer array monotonic scan interview pattern is the O(n) solution. The key insight: right = last position where the running maximum from the left exceeds the current element; left = first position where the running minimum from the right is less than the current element. Meta and Adobe interviewers test the distinction between the sorting approach and the O(n) approach. Know both — state the O(n log n) sorting approach first, then optimize to O(n). This establishes analytical thinking before diving into code.