Problem

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

OR

Give a list of unsorted number, find the min window or min sublist or min subarray of the input, such as if sublist is sorted, the whole list is sorted too.

Examples

Example 1:

1
2
3

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:

1
2

Input: nums = [1,2,3,4]
Output: 0

Example 3:

1
2

Input: nums = [1]
Output: 0

Solution

The idea is to assume left part and right part of array is somehow sorted. WE have to find hte unsorted array somewhere in the middle.

Method 1 - Sorting and Comparing

Intuition

If we sort the array, the sorted version will show us which elements are out of place. By comparing the original and sorted arrays, we can find the boundaries of the shortest subarray that needs sorting.

Approach

  1. Copy and sort the input array.
  2. Compare the original and sorted arrays from both ends to find the first and last indices where they differ.
  3. The subarray between these indices is the minimal window that must be sorted.
  4. If the array is already sorted, return 0.

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting the array dominates.
  • 🧺 Space complexity: O(n) — Copy of the array for sorting.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	public int findUnsortedSubarray(int[] nums) {
		int n = nums.length;
		int[] sortedNums = Arrays.copyOf(nums, n);
		Arrays.sort(sortedNums);
		int start = 0;
		while (start < n && nums[start] == sortedNums[start]) start++;
		int end = n - 1;
		while (end > start && nums[end] == sortedNums[end]) end--;
		return end - start + 1;
	}
}
1
2
3
4
5
6
7
8
9

class Solution:
	def findUnsortedSubarray(self, 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
1

class Solution {

Method 2 - Greedy (No Sorting)

Intuition

Instead of sorting, we can scan from both ends to find the boundaries of the unsorted subarray. By tracking the maximum and minimum values while traversing, we can identify where the order breaks and thus the minimal window to sort.

Approach

  1. Traverse from left to right, tracking the running maximum. If an element is less than the max, update the right boundary.
  2. Traverse from right to left, tracking the running minimum. If an element is greater than the min, update the left boundary.
  3. The window between left and right is the shortest unsorted subarray.
  4. If the array is already sorted, return 0.

Complexity

  • ⏰ Time complexity: O(n) — Single pass from both ends.
  • 🧺 Space complexity: O(1) — Only variables for boundaries and min/max.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	public int findUnsortedSubarray(int[] nums) {
		int n = nums.length;
		int left = n - 1, right = 0;
		int max = nums[0], min = nums[n - 1];
		for (int i = 0; i < n; ++i) {
			max = Math.max(max, nums[i]);
			if (nums[i] < max) right = i;
		}
		for (int i = n - 1; i >= 0; --i) {
			min = Math.min(min, nums[i]);
			if (nums[i] > min) left = i;
		}
		if (right <= left) return 0;
		return right - left + 1;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
	def findUnsortedSubarray(self, nums):
		n = len(nums)
		left, right = n - 1, 0
		max_num, min_num = nums[0], nums[-1]
		for i in range(n):
			max_num = max(max_num, nums[i])
			if nums[i] < max_num:
				right = i
		for i in range(n - 1, -1, -1):
			min_num = min(min_num, nums[i])
			if nums[i] > min_num:
				left = i
		if right <= left:
			return 0
		return right - left + 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
	int findUnsortedSubarray(vector<int>& nums) {
		int n = nums.size();
		int left = n - 1, right = 0;
		int max_num = nums[0], min_num = nums[n - 1];
		for (int i = 0; i < n; ++i) {
			max_num = max(max_num, nums[i]);
			if (nums[i] < max_num) right = i;
		}
		for (int i = n - 1; i >= 0; --i) {
			min_num = min(min_num, nums[i]);
			if (nums[i] > min_num) left = i;
		}
		if (right <= left) return 0;
		return right - left + 1;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func findUnsortedSubarray(nums []int) int {
	n := len(nums)
	left, right := n-1, 0
	maxNum, minNum := nums[0], nums[n-1]
	for i := 0; i < n; i++ {
		if nums[i] < maxNum {
			right = i
		}
		if nums[i] > maxNum {
			maxNum = nums[i]
		}
	}
	for i := n-1; i >= 0; i-- {
		if nums[i] > minNum {
			left = i
		}
		if nums[i] < minNum {
			minNum = nums[i]
		}
	}
	if right <= left {
		return 0
	}
	return right - left + 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
	fun findUnsortedSubarray(nums: IntArray): Int {
		val n = nums.size
		var left = n - 1
		var right = 0
		var maxNum = nums[0]
		var minNum = nums[n - 1]
		for (i in 0 until n) {
			maxNum = maxOf(maxNum, nums[i])
			if (nums[i] < maxNum) right = i
		}
		for (i in n - 1 downTo 0) {
			minNum = minOf(minNum, nums[i])
			if (nums[i] > minNum) left = i
		}
		if (right <= left) return 0
		return right - left + 1
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
	pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
		let n = nums.len();
		let mut left = n - 1;
		let mut right = 0;
		let mut max_num = nums[0];
		let mut min_num = nums[n - 1];
		for i in 0..n {
			max_num = max_num.max(nums[i]);
			if nums[i] < max_num {
				right = i;
			}
		}
		for i in (0..n).rev() {
			min_num = min_num.min(nums[i]);
			if nums[i] > min_num {
				left = i;
			}
		}
		if right <= left {
			return 0;
		}
		(right - left + 1) as i32
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	findUnsortedSubarray(nums: number[]): number {
		const n = nums.length;
		let left = n - 1, right = 0;
		let maxNum = nums[0], minNum = nums[n - 1];
		for (let i = 0; i < n; i++) {
			maxNum = Math.max(maxNum, nums[i]);
			if (nums[i] < maxNum) right = i;
		}
		for (let i = n - 1; i >= 0; i--) {
			minNum = Math.min(minNum, nums[i]);
			if (nums[i] > minNum) left = i;
		}
		if (right <= left) return 0;
		return right - left + 1;
	}
}