Shortest Unsorted Continuous Subarray - Solution & Explanation
Problem Statement
Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.
Return the shortest such subarray and output its length.
Example 1:
Input: nums = [2,6,4,8,10,9,15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Example 2:
Input: nums = [1,2,3,4] Output: 0
Example 3:
Input: nums = [1] Output: 0
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 105
Follow up: Can you solve it in
O(n) time complexity?Approach Overview
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.
Approach 1: Using Sorting to Identify Subarray
We can sort a copy of the array and compare it with the original array to determine the boundaries of the subarray that needs to be sorted.
Sort the array and compare with the original array from the start and end to find the first and last mismatch. These mismatches will give the boundaries of the subarray.
The function makes a copy of the array, sorts it, and then compares it with the original array. It finds the first and last indices where the two arrays differ. If such indices are found, the length of the subarray is returned; otherwise, it's zero.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing a copy of the array.
Approach 2: Single Pass Scan for Minimum and Maximum Deviations
In this approach, we aim to find the shortest unsorted subarray by utilizing two passes to find the minimum and maximum deviations from the sorted order.
- Traverse from left to right to find the rightmost boundary where the unsorted order occurs by keeping track of the maximum seen value.
- Traverse from right to left to find the leftmost boundary by keeping track of the minimum seen value.
The range between these two boundaries produces the result.
The idea is to use two scans of the array to find maximum and minimum deviation points. The logic helps in computing boundaries by tracking the range that is unsorted and quickly determines the shortest unsorted subarray.
Complexity
Time Complexity: O(n) as it processes the array twice.
Space Complexity: O(1) since no additional space is used apart from basic variables.
Approach 3: Sorting
We can first sort the array, and then compare the sorted array with the original array to find the leftmost and rightmost positions where they differ. The length between them is the length of the shortest unsorted continuous subarray.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array.
Approach 4: Maintaining the Maximum Value on the Left and the Minimum Value on the Right
We can traverse the array from left to right and maintain a maximum value mx. If the current value is less than mx, it means that the current value is not in the correct position, and we update the right boundary r to the current position. Similarly, we can traverse the array from right to left and maintain a minimum value mi. If the current value is greater than mi, it means that the current value is not in the correct position, and we update the left boundary l to the current position. At initialization, we set l and r to -1. If l and r are not updated, it means that the array is already sorted, and we return 0. Otherwise, we return r - l + 1.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Sorting to Identify Subarray | Time Complexity: O(n log n) due to sorting. |
| Single Pass Scan for Minimum and Maximum Deviations | Time Complexity: O(n) as it processes the array twice. |
| Sorting | — |
| Maintaining the Maximum Value on the Left and the Minimum Value on the Right | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Compare | O(n log n) | O(n) | Simplest implementation; good for explaining the problem logic first |
| Single Pass Min/Max Scan | O(n) | O(1) | Optimal solution expected in interviews; constant extra space |
| Monotonic Stack Boundaries | O(n) | O(n) | Useful when practicing monotonic stack patterns for array order problems |
Video Solution
LeetCode 581. Shortest Unsorted Continuous Subarray (Algorithm Explained) • Nick White • 21,583 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shortest Unsorted Continuous Subarray easy or hard?
How to solve Shortest Unsorted Continuous Subarray in O(n)?
What is the best approach for Shortest Unsorted Continuous Subarray?
What data structure is used in Shortest Unsorted Continuous Subarray?
What is the time complexity of Shortest Unsorted Continuous Subarray?
Shortest Unsorted Continuous Subarray Python or Java solution approach?
Is Shortest Unsorted Continuous Subarray asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Shortest Unsorted Continuous Subarray with our built-in code editor and test cases.
Practice on FleetCode