Shortest Unsorted Continuous Subarray
MedPrompt
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: 0Example 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?Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves creating a sorted version of the input array and comparing it with the original array. The boundaries of the required subarray are determined by the first and last positions where the elements of the original array and the sorted array do not match.
Algorithm
- Create a clone of the input array
numsand name itsorted_nums. - Sort the
sorted_numsarray in non-decreasing order. - If
numsis identical tosorted_nums, the array is already sorted, so return 0. - Find the first index from the left,
left, wherenums[left]differs fromsorted_nums[left]. - Find the first index from the right,
right, wherenums[right]differs fromsorted_nums[right]. - The length of the shortest unsorted subarray is
right - left + 1.
Walkthrough
The most straightforward way to identify the unsorted portion of an array is to have a sorted version of it for reference. By comparing the original array nums with its sorted counterpart, we can pinpoint exactly which elements are out of place.
We start by creating a copy of nums and sorting it. Then, we iterate from both ends of the arrays inward. The first index from the left where nums[i] and sorted_nums[i] are different gives us the left boundary of the unsorted subarray. Similarly, the first mismatch from the right gives us the right boundary. If no mismatches are found, the array is already sorted, and the length is 0. Otherwise, the result is the distance between these two boundaries, inclusive.
import java.util.Arrays; class Solution { public int findUnsortedSubarray(int[] nums) { int[] sorted_nums = nums.clone(); Arrays.sort(sorted_nums); int start = nums.length, end = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != sorted_nums[i]) { start = Math.min(start, i); end = Math.max(end, i); } } if (end - start >= 0) { return end - start + 1; } else { return 0; } }}Complexity
Time
O(n log n) - The dominant operation is sorting the array, which typically takes `O(n log n)` time. The subsequent linear scans take `O(n)` time.
Space
O(n) - A copy of the input array is created for sorting, which requires space proportional to the number of elements, `n`.
Trade-offs
Pros
Simple to conceptualize and implement.
Correctly handles all edge cases, including already sorted arrays.
Cons
The time complexity is dominated by the sorting algorithm, making it slower than linear-time solutions.
Requires extra space proportional to the input array size to hold the sorted copy.
A more efficient approach uses a stack to determine the boundaries of the unsorted subarray in a single pass for each boundary. By maintaining a monotonic stack (increasing for the left boundary, decreasing for the right boundary), we can identify the indices of elements that violate the sorted order and find the outermost such indices.
Algorithm
- Initialize
left = n(wherenis the array length) andright = -1. - First Pass (to find
left):- Use a stack to keep track of indices in increasing order of their corresponding values.
- Iterate through the array from left to right. For each element
nums[i], if it's smaller than the value at the index on top of the stack, it means the top element is out of place. Pop from the stack and updateleft = min(left, popped_index). - Push the current index
ionto the stack.
- Second Pass (to find
right):- Clear the stack.
- Use the stack to keep track of indices in decreasing order of their corresponding values.
- Iterate through the array from right to left. For each element
nums[i], if it's larger than the value at the index on top of the stack, pop and updateright = max(right, popped_index). - Push the current index
ionto the stack.
- If
right > left, the length isright - left + 1. Otherwise, the array is sorted, and the length is 0.
Walkthrough
This method cleverly uses a stack to find the correct boundaries left and right in linear time.
To find the left boundary, we iterate from the beginning of the array. We maintain a stack of indices whose corresponding elements are in increasing order. When we encounter an element nums[i] that is smaller than the element at the stack's top, it signifies a disorder. The element at the stack's top is too large for its position and must be part of the unsorted subarray. We pop from the stack and update our candidate for the left boundary (left) with the popped index. We continue this until the stack top is smaller than nums[i] or the stack is empty. This ensures left is the smallest index of an element that is larger than some element to its right.
To find the right boundary, we perform a symmetric operation, iterating from the end of the array. We maintain a stack of indices for elements in decreasing order. When we find an element nums[i] larger than the stack's top, we know the top element is too small for its position. We pop and update the right boundary (right).
import java.util.Stack; class Solution { public int findUnsortedSubarray(int[] nums) { Stack<Integer> stack = new Stack<>(); int left = nums.length, right = -1; // Find the left boundary for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { left = Math.min(left, stack.pop()); } stack.push(i); } stack.clear(); // Find the right boundary for (int i = nums.length - 1; i >= 0; i--) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { right = Math.max(right, stack.pop()); } stack.push(i); } return right > left ? right - left + 1 : 0; }}Complexity
Time
O(n) - The algorithm consists of two separate passes through the array. In each pass, every element is pushed onto and popped from the stack at most once.
Space
O(n) - In the worst-case scenario (e.g., a fully sorted array), the stack can grow to hold all `n` indices.
Trade-offs
Pros
Achieves optimal O(n) time complexity.
Provides an elegant way to find boundaries by identifying out-of-order elements.
Cons
Requires O(n) extra space for the stack, which is less optimal than a constant space solution.
This optimal approach solves the problem in linear time and constant space. It works by first identifying the minimum and maximum values that are out of their sorted positions. Then, it determines the correct placement for these values, which in turn defines the boundaries of the shortest unsorted continuous subarray.
Algorithm
- Initialize
min_val = Integer.MAX_VALUEandmax_val = Integer.MIN_VALUE. - Step 1: Find the minimum and maximum of the disordered subarray.
- Iterate from
i = 1ton-1. Ifnums[i] < nums[i-1], we've found a dip. Thisnums[i]is part of the unsorted section. Updatemin_val = min(min_val, nums[i]). - Iterate from
i = n-2down to0. Ifnums[i] > nums[i+1], we've found a peak. Thisnums[i]is part of the unsorted section. Updatemax_val = max(max_val, nums[i]).
- Iterate from
- If
min_valremainsInteger.MAX_VALUE, the array is already sorted; return 0. - Step 2: Find the correct boundaries for
min_valandmax_val.- Find the left boundary
leftby iterating from the start of the array.leftis the first indexlwherenums[l] > min_val. - Find the right boundary
rightby iterating from the end of the array.rightis the first indexrwherenums[r] < max_val.
- Find the left boundary
- The result is
right - left + 1.
Walkthrough
The key insight is that the subarray we need to sort is bounded by the correct positions of the smallest and largest out-of-place numbers.
The algorithm proceeds in two main stages:
-
Find the range of values in the unsorted subarray: We can find the minimum element (
min_val) that is out of place by finding any element that is smaller than its preceding element. Similarly, the maximum element (max_val) that is out of place can be found by identifying any element larger than its succeeding element. We iterate through the array to find the absolute minimum and maximum of all such out-of-place elements. -
Find the boundaries of the subarray: Once we have
min_valandmax_val, the entire subarray fromnums[0]up to the correct position ofmax_valmight need reordering. Likewise, the subarray from the correct position ofmin_valto the end might need reordering. Therefore, the left boundary of our final subarray is the first index from the left that is greater thanmin_val. The right boundary is the first index from the right that is less thanmax_val.
This method requires a few passes over the array but uses only a constant amount of extra space for variables.
class Solution { public int findUnsortedSubarray(int[] nums) { int min_val = Integer.MAX_VALUE; int max_val = Integer.MIN_VALUE; boolean flag = false; // Find the minimum element of the unsorted subarray for (int i = 1; i < nums.length; i++) { if (nums[i] < nums[i - 1]) { flag = true; } if (flag) { min_val = Math.min(min_val, nums[i]); } } flag = false; // Find the maximum element of the unsorted subarray for (int i = nums.length - 2; i >= 0; i--) { if (nums[i] > nums[i + 1]) { flag = true; } if (flag) { max_val = Math.max(max_val, nums[i]); } } if (min_val == Integer.MAX_VALUE) { // Array is sorted return 0; } int left, right; // Find the correct position for min_val (left boundary) for (left = 0; left < nums.length; left++) { if (nums[left] > min_val) { break; } } // Find the correct position for max_val (right boundary) for (right = nums.length - 1; right >= 0; right--) { if (nums[right] < max_val) { break; } } return right - left + 1; }}Complexity
Time
O(n) - The algorithm involves a constant number of passes (four in this implementation) over the array, resulting in a linear time complexity.
Space
O(1) - The algorithm uses a fixed number of variables to store the minimum and maximum values and the boundaries, regardless of the input size.
Trade-offs
Pros
Most efficient solution with O(n) time and O(1) space complexity.
Avoids the overhead of data structures like stacks or creating array copies.
Cons
The logic can be less intuitive to come up with compared to the sorting approach.
It requires multiple passes over the array, though the overall complexity remains linear.
Solutions
Solution
class Solution {public int findUnsortedSubarray(int[] nums) { final int inf = 1 << 30; int n = nums.length; int l = -1, r = -1; int mi = inf, mx = -inf; for (int i = 0; i < n; ++i) { if (mx > nums[i]) { r = i; } else { mx = nums[i]; } if (mi < nums[n - i - 1]) { l = n - i - 1; } else { mi = nums[n - i - 1]; } } return r == -1 ? 0 : r - l + 1; }}class Solution {public: int findUnsortedSubarray(vector<int> &nums) { const int inf = 1e9; int n = nums.size(); int l = -1, r = -1; int mi = inf, mx = -inf; for (int i = 0; i < n; ++i) { if (mx > nums[i]) { r = i; } else { mx = nums[i]; } if (mi < nums[n - i - 1]) { l = n - i - 1; } else { mi = nums[n - i - 1]; } } return r == -1 ? 0 : r - l + 1; }};class Solution: def findUnsortedSubarray(self, nums: List[int]) -> int: mi, mx = inf, - inf l = r = - 1 n = len(nums) for i, x in enumerate(nums): if mx > x: r = i else: mx = x if mi < nums[n - i - 1]: l = n - i - 1 else: mi = nums[n - i - 1] return 0 if r == - 1 else r - l + 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.