Shortest Unsorted Continuous Subarray solution and explanation
Deloitte
Google
9 more videos on this problem
LeetCode 581. Shortest Unsorted Continuous Subarray (Algorithm Explained)Nick White · 8:25 · 21K views
Leetcode 581. Shortest Unsorted Continuous Subarray || Intuition + Example + CodeCode with Alisha · 18:38 · 8K views
Shortest Unsorted Continuous Subarray | Leetcode 581 | Two pointers | Day-3Ayushi Sharma · 13:55 · 7K views
Shortest Unsorted Continuous Subarray | Live Coding with Explanation | Leetcode - 581Algorithms Made Easy · 10:20 · 5K views
Leetcode 581. Shortest Unsorted Continuous Subarray [ Solution + Code Explained]jayati tiwari · 14:36 · 4K views
Leetcode Visualized: 581. Shortest Unsorted Continuous SubarrayAlexander Le · 13:47 · 3K views
Leetcode - Shortest Unsorted Continuous Subarray (Python)Timothy H Chang · 8:49 · 2K views
Shortest Unsorted Continuous Subarray | Leetcode 581 | Monotonic Stack | Live coding sessionCoding Decoded · 14:27 · 2K views
LeetCode 581. Shortest Unsorted Continuous SubarrayHappy Coding · 17:12 · 993 views
Daily Leetcode #763: May 03, 2022 - 581. Shortest Unsorted Continuous SubarrayProgramming Live with Larry · 14:01 · 558 views
The problem
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
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.
def findUnsortedSubarray(nums):
sorted_nums = sorted(nums)
start, end = 0, len(nums) - 1
while start < len(nums) and nums[start] == sorted_nums[start]:
start += 1
while end > start and nums[end] == sorted_nums[end]:
end -= 1
return end - start + 1 if start < end else 0
# Example usage
nums = [2, 6, 4, 8, 10, 9, 15]
print(findUnsortedSubarray(nums)) # Output: 5import java.util.Arrays;
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int start = 0, end = nums.length - 1;
while (start < nums.length && nums[start] == sorted[start]) {
start++;
}
while (end > start && nums[end] == sorted[end]) {
end--;
}
return start < end ? end - start + 1 : 0;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 6, 4, 8, 10, 9, 15};
System.out.println(solution.findUnsortedSubarray(nums)); // Output: 5
}
}#include <iostream>
#include <vector>
#include <algorithm>
int findUnsortedSubarray(std::vector<int>& nums) {
std::vector<int> sorted(nums);
std::sort(sorted.begin(), sorted.end());
int start = 0, end = nums.size() - 1;
while (start < nums.size() && nums[start] == sorted[start]) {
++start;
}
while (end > start && nums[end] == sorted[end]) {
--end;
}
return start < end ? end - start + 1 : 0;
}
int main() {
std::vector<int> nums = {2, 6, 4, 8, 10, 9, 15};
std::cout << findUnsortedSubarray(nums) << std::endl; // Output: 5
return 0;
}function findUnsortedSubarray(nums) {
const sorted = [...nums].sort((a, b) => a - b);
let start = 0, end = nums.length - 1;
while (start < nums.length && nums[start] === sorted[start]) {
start++;
}
while (end > start && nums[end] === sorted[end]) {
end--;
}
return start < end ? end - start + 1 : 0;
}
// Example usage:
const nums = [2, 6, 4, 8, 10, 9, 15];
console.log(findUnsortedSubarray(nums)); // Output: 5#include <stdio.h>
#include <stdlib.h>
int findUnsortedSubarray(int* nums, int numsSize) {
int* sorted = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
sorted[i] = nums[i];
}
qsort(sorted, numsSize, sizeof(int), compare);
int start = 0, end = numsSize - 1;
while (start < numsSize && nums[start] == sorted[start]) {
start++;
}
while (end > start && nums[end] == sorted[end]) {
end--;
}
free(sorted);
return start < end ? end - start + 1 : 0;
}
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int arr[] = {2, 6, 4, 8, 10, 9, 15};
int length = findUnsortedSubarray(arr, 7);
printf("%d\n", length); // Output: 5
return 0;
}using System;
using System.Linq;
public class Solution {
public int FindUnsortedSubarray(int[] nums) {
int[] sorted = nums.ToArray();
Array.Sort(sorted);
int start = 0, end = nums.Length - 1;
while (start < nums.Length && nums[start] == sorted[start]) {
start++;
}
while (end > start && nums[end] == sorted[end]) {
end--;
}
return start < end ? end - start + 1 : 0;
}
public static void Main(string[] args) {
var solution = new Solution();
int[] nums = {2, 6, 4, 8, 10, 9, 15};
Console.WriteLine(solution.FindUnsortedSubarray(nums)); // Output: 5
}
}In Python, sorted copies the list and sorts it. We iterate from the start and end to find where the numbers differ and calculate the length of that interval.
Time Complexity: O(n log n) for the sort.
Space Complexity: O(n) for the sorted list.
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.
def findUnsortedSubarray(nums):
start, end = -1, -2
max_val, min_val = nums[0], nums[-1]
for i in range(len(nums)):
max_val = max(max_val, nums[i])
min_val = min(min_val, nums[len(nums) - 1 - i])
if nums[i] < max_val:
end = i
if nums[len(nums) - 1 - i] > min_val:
start = len(nums) - 1 - i
return end - start + 1
# Example usage
nums = [2, 6, 4, 8, 10, 9, 15]
print(findUnsortedSubarray(nums)) # Output: 5public class Solution {
public int findUnsortedSubarray(int[] nums) {
int start = -1, end = -2;
int max = nums[0], min = nums[nums.length - 1];
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[nums.length - 1 - i]);
if (nums[i] < max) end = i;
if (nums[nums.length - 1 - i] > min) start = nums.length - 1 - i;
}
return end - start + 1;
}
public static void main(String[] args) {
int[] nums = {2, 6, 4, 8, 10, 9, 15};
Solution solution = new Solution();
System.out.println(solution.findUnsortedSubarray(nums)); // Output: 5
}
}#include <vector>
#include <iostream>
#include <algorithm>
int findUnsortedSubarray(std::vector<int>& nums) {
int start = -1, end = -2;
int max = nums[0], min = nums[nums.size() - 1];
for (int i = 0; i < nums.size(); i++) {
max = std::max(max, nums[i]);
min = std::min(min, nums[nums.size() - i - 1]);
if (nums[i] < max) end = i;
if (nums[nums.size() - i - 1] > min) start = nums.size() - i - 1;
}
return end - start + 1;
}
int main() {
std::vector<int> nums = {2, 6, 4, 8, 10, 9, 15};
std::cout << findUnsortedSubarray(nums) << std::endl; // Output: 5
return 0;
}function findUnsortedSubarray(nums) {
let start = -1, end = -2;
let max = nums[0], min = nums[nums.length - 1];
for (let i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[nums.length - 1 - i]);
if (nums[i] < max) end = i;
if (nums[nums.length - 1 - i] > min) start = nums.length - 1 - i;
}
return end - start + 1;
}
// Example usage
const nums = [2, 6, 4, 8, 10, 9, 15];
console.log(findUnsortedSubarray(nums)); // Output: 5#include <stdio.h>
int findUnsortedSubarray(int* nums, int numsSize) {
int start = -1, end = -2, max = nums[0], min = nums[numsSize - 1];
for (int i = 0; i < numsSize; i++) {
max = max > nums[i] ? max : nums[i];
min = min < nums[numsSize - i - 1] ? min : nums[numsSize - i - 1];
if (nums[i] < max) end = i;
if (nums[numsSize - i - 1] > min) start = numsSize - i - 1;
}
return end - start + 1;
}
int main() {
int arr[] = {2, 6, 4, 8, 10, 9, 15};
int length = findUnsortedSubarray(arr, 7);
printf("%d\n", length); // Output: 5
return 0;
}using System;
public class Solution {
public int FindUnsortedSubarray(int[] nums) {
int start = -1, end = -2;
int max = nums[0], min = nums[nums.Length - 1];
for (int i = 0; i < nums.Length; i++) {
max = Math.Max(max, nums[i]);
min = Math.Min(min, nums[nums.Length - 1 - i]);
if (nums[i] < max) end = i;
if (nums[nums.Length - 1 - i] > min) start = nums.Length - 1 - i;
}
return end - start + 1;
}
public static void Main(string[] args) {
int[] nums = {2, 6, 4, 8, 10, 9, 15};
var sol = new Solution();
Console.WriteLine(sol.FindUnsortedSubarray(nums)); // Output: 5
}
}This Python version executes the double-pass strategy by determining two boundaries of minimum and maximum deviations across the entire array to ascertain the unsorted subarray.
Time Complexity: O(n) because it efficiently computes the result through passes.
Space Complexity: O(1), requiring no additional storing structures.
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.
function findUnsortedSubarray(nums: number[]): number {
const arr = [...nums];
arr.sort((a, b) => a - b);
let [l, r] = [0, arr.length - 1];
while (l <= r && arr[l] === nums[l]) {
++l;
}
while (l <= r && arr[r] === nums[r]) {
--r;
}
return r - l + 1;
}func findUnsortedSubarray(nums []int) int {
arr := make([]int, len(nums))
copy(arr, nums)
sort.Ints(arr)
l, r := 0, len(arr)-1
for l <= r && nums[l] == arr[l] {
l++
}
for l <= r && nums[r] == arr[r] {
r--
}
return r - l + 1
}impl Solution {
pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
let mut arr = nums.clone();
arr.sort();
let mut l = 0usize;
while l < nums.len() && nums[l] == arr[l] {
l += 1;
}
if l == nums.len() {
return 0;
}
let mut r = nums.len() - 1;
while r > l && nums[r] == arr[r] {
r -= 1;
}
(r - l + 1) as i32
}
}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.
function findUnsortedSubarray(nums: number[]): number {
let [l, r] = [-1, -1];
let [mi, mx] = [Infinity, -Infinity];
const n = nums.length;
for (let 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;
}func findUnsortedSubarray(nums []int) int {
const inf = 1 << 30
n := len(nums)
l, r := -1, -1
mi, mx := inf, -inf
for i, x := range 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]
}
}
if r == -1 {
return 0
}
return r - l + 1
}impl Solution {
pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
let inf = 1 << 30;
let n = nums.len();
let mut l = -1;
let mut r = -1;
let mut mi = inf;
let mut mx = -inf;
for i in 0..n {
if mx > nums[i] {
r = i as i32;
} else {
mx = nums[i];
}
if mi < nums[n - i - 1] {
l = (n - i - 1) as i32;
} else {
mi = nums[n - i - 1];
}
}
if r == -1 {
0
} else {
r - l + 1
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Sorting to Identify Subarray | Time Complexity: O(n log n) for the sort. |
| Single Pass Scan for Minimum and Maximum Deviations | Time Complexity: O(n) because it efficiently computes the result through passes. |
| Sorting | – |
| Maintaining the Maximum Value on the Left and the Minimum Value on the Right | – |
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 |
Frequently asked questions
Is Shortest Unsorted Continuous Subarray easy or hard?
Shortest Unsorted Continuous Subarray is classified as a Medium problem on LeetCode. The difficulty comes from recognizing that you can detect disorder using running minimum and maximum values instead of sorting the entire array.
How to solve Shortest Unsorted Continuous Subarray in O(n)?
Scan from the left while maintaining the maximum value seen so far. Whenever the current element is smaller than this maximum, update the right boundary. Then scan from the right while maintaining the minimum value; when the current element exceeds it, update the left boundary. The segment between these boundaries is the answer.
What is the best approach for Shortest Unsorted Continuous Subarray?
The best approach is the linear scan using minimum and maximum deviations. Traverse left to right while tracking the maximum value to detect the right boundary, then traverse right to left tracking the minimum value to find the left boundary. This method runs in O(n) time and uses O(1) extra space.
What data structure is used in Shortest Unsorted Continuous Subarray?
Most solutions rely only on basic array traversal with running minimum and maximum values. Some implementations also use a monotonic stack to detect ordering violations, which helps identify the left and right boundaries of the unsorted segment.
What is the time complexity of Shortest Unsorted Continuous Subarray?
The optimal solution runs in O(n) time with O(1) extra space using two directional scans. A simpler alternative sorts a copy of the array and compares positions, which takes O(n log n) time and O(n) space.
Shortest Unsorted Continuous Subarray Python or Java solution approach?
Both Python and Java implementations typically use the O(n) greedy scan. Track a running maximum during a forward pass and a running minimum during a backward pass to identify boundaries. The algorithm uses constant extra space and works efficiently for large arrays.
Is Shortest Unsorted Continuous Subarray asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving array order violations and greedy boundary detection. Variants of this question appear in interviews at large tech companies such as Amazon, Google, and Meta because it tests array reasoning and linear-time optimization.