Log inSign up
mediumLeetCodeNot Started

Shortest Unsorted Continuous Subarray

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Unsorted Subarray:

Input: nums = [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: Sorting subarray [6, 4, 8, 10, 9] (indices 1 to 5) gives [2, 4, 6, 8, 9, 10, 15]. Length is 5.

Example 2 · Already Sorted Array:

Input: nums = [1, 2, 3, 4]
Output: 0
Explanation: Array is already sorted, so length is 0.

Example 3 · Single Element Array:

Input: nums = [1]
Output: 0
Explanation: Array of length 1 is already sorted.

Constraints:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Monotonicity checks
  • Two-pass array scanning

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify left and right boundaries of disordered subarrays.
  • Formulate two-pass prefix-max and suffix-min invariants.
  • Eliminate extra memory overhead to achieve O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Track maxFromLeft: if nums[i] < maxFromLeft -> right = i.
  • Track minFromRight: if nums[j] > minFromRight -> left = j.
  • Result = right >= left ? right - left + 1 : 0.

Connected Patterns:

Trapping Rain Water (Prefix max / suffix min)Next Greater Element

1. Check All Subarrays (Brute Force)

Intuition

Iterate through all pairs (i, j) with 0 <= i <= j < n. For each pair, create a copy of nums, sort the segment from i to j, and check if the entire array is sorted. The smallest difference j - i + 1 among all valid pairs is the answer.

When to apply: Use to understand the minimal contiguous unsorted window definition.

Brute Force Window Validation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 6, 4, 8, 10, 9, 15]
Current operationSTEP 1 OF 6
Array: [2, 6, 4, 8, 10, 9, 15]
Visual state
Values and pointers at this exact step
array
S
2
6
4
8
10
9
15
0
↑ Start
1
2
3
4
5
6
Variables at this step
arr
[2,6,4,8,10,9,15]
n
7
Check / comparison
Array is not sorted.
Decision / next transition
Search for shortest window.
Why this step matters

Array: [2, 6, 4, 8, 10, 9, 15]. Full length n = 7.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int findUnsortedSubarray(int[] nums) {
4 int n = nums.length;
5 int minLen = n;
6 for (int i = 0; i < n; i++) {
7 for (int j = i; j < n; j++) {
8 int[] copy = nums.clone();
9 java.util.Arrays.sort(copy, i, j + 1);
10 if (isSorted(copy)) {
11 minLen = Math.min(minLen, j - i + 1);
12 }
13 }
14 }
15 return isSorted(nums) ? 0 : minLen;
16 }
17
18 private boolean isSorted(int[] arr) {
19 for (int i = 0; i < arr.length - 1; i++) {
20 if (arr[i] > arr[i + 1]) return false;
21 }
22 return true;
23 }
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int[] nums = {2, 6, 4, 8, 10, 9, 15};
29 System.out.println("Shortest Unsorted Subarray: " + sol.findUnsortedSubarray(nums));
30 }
31}

Time & Space Complexity

  • Time complexity: O(n^3) — O(n2) pairs, each requiring an O(n log n) or O(n) validation.
  • Space complexity: O(n) — O(n) memory to store the copied array for verification.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Comparison with Sorted Array (Better)

Intuition

1. Create sorted copy: s = sorted(nums). 2. Find leftmost index l where nums[l] != s[l]. 3. Find rightmost index r where nums[r] != s[r]. 4. If array is already sorted, r <= l; return 0. Otherwise, return r - l + 1.

When to apply: Use when an O(n log n) solution with O(n) memory is acceptable.

Sorted Array Mismatch Comparison Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 6, 4, 8, 10, 9, 15]
Current operationSTEP 1 OF 6
nums: [2, 6, 4, 8, 10, 9, 15]
Visual state
Values and pointers at this exact step
pointers
S
2
6
4
8
10
9
15
0
1
↑ Scan l
2
3
4
5
6
Variables at this step
l
0
r
6
Check / comparison
Index 0: nums[0] == sorted[0] == 2
Decision / next transition
Index 0 matches. Move left pointer to index 1.
Why this step matters

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

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.Arrays;
2
3public class Main {
4 public static class Solution {
5 public int findUnsortedSubarray(int[] nums) {
6 int[] sorted = nums.clone();
7 Arrays.sort(sorted);
8 int l = 0, r = nums.length - 1;
9 while (l < nums.length && nums[l] == sorted[l]) l++;
10 while (r > l && nums[r] == sorted[r]) r--;
11 return r - l + 1;
12 }
13 }
14
15 public static void main(String[] args) {
16 Solution sol = new Solution();
17 int[] nums = {2, 6, 4, 8, 10, 9, 15};
18 System.out.println("Shortest Unsorted Subarray: " + sol.findUnsortedSubarray(nums));
19 }
20}

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting the array takes O(n log n), followed by two O(n) scans.
  • Space complexity: O(n) — O(n) auxiliary memory for the sorted copy.

3. Two-Pass Extremum Invariant (Optimal)

Intuition

1. An element nums[i] is correctly placed on the left if it is greater than all elements before it, and smaller than all elements after it. 2. Scanning left-to-right: track maxSeen. Any element with nums[i] < maxSeen is out of order; the last such element defines right boundary r. 3. Scanning right-to-left: track minSeen. Any element with nums[i] > minSeen is out of order; the last such element defines left boundary l. 4. If r == -1, array is sorted, return 0; else return r - l + 1.

When to apply: Use as the optimal O(n) time, O(1) space gold standard solution.

Two-Pass Extremum Interactive Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 6, 4, 8, 10, 9, 15]
Current operationSTEP 1 OF 6
Step 1: Initialize l = -1, r = -1, maxSeen = -Infinity, minSeen = Infinity
Visual state
Values and pointers at this exact step
pointers
S
2
6
4
8
10
9
15
0
↑ Start
1
2
3
4
5
6
Variables at this step
l
-1
r
-1
Check / comparison
Start left-to-right pass for right boundary.
Decision / next transition
Begin scan.
Why this step matters

Step 1: Initialize l = -1, r = -1, maxSeen = -Infinity, minSeen = Infinity. Array = [2, 6, 4, 8, 10, 9, 15].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int findUnsortedSubarray(int[] nums) {
4 int n = nums.length;
5 int maxSeen = nums[0], r = -1;
6 for (int i = 1; i < n; i++) {
7 if (nums[i] < maxSeen) {
8 r = i;
9 } else {
10 maxSeen = nums[i];
11 }
12 }
13
14 int minSeen = nums[n - 1], l = -1;
15 for (int i = n - 2; i >= 0; i--) {
16 if (nums[i] > minSeen) {
17 l = i;
18 } else {
19 minSeen = nums[i];
20 }
21 }
22
23 return r == -1 ? 0 : r - l + 1;
24 }
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 int[] nums = {2, 6, 4, 8, 10, 9, 15};
30 System.out.println("Shortest Unsorted Subarray: " + sol.findUnsortedSubarray(nums));
31 }
32}

Time & Space Complexity

  • Time complexity: O(n) — Two simple linear passes through the array take O(n) total operations.
  • Space complexity: O(1) — O(1) memory for scalar tracking variables (maxSeen, minSeen, l, r).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Try All SubarraysO(N^3) or O(N^2)O(N)Check all pairs (i, j), sort subarray, and verify if whole array is sorted.Tests O(N2) subarray intervals.
2.Better — Compare with Sorted ArrayO(N log N)O(N)Create a sorted copy. Find first and last index where original differs from sorted.Sorting copy array.
3.Optimal — Two-Pass Min/Max Boundary TrackingOptimalO(N)O(1)Scan left-to-right tracking max to find right boundary; scan right-to-left tracking min to find left boundary.Optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Shortest Unsorted Continuous Subarray?

2.Why is the brute force approach suboptimal for large inputs in Shortest Unsorted Continuous Subarray?

3.Which data structure or technique enables the optimal solution for Shortest Unsorted Continuous Subarray?

Back to DSA Sheet