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

Variant

Variant 1 - Return the bounds instead of length

Instead of returning right - left + 1, return (left, right) where left and right are the start and end indices of the unsorted window. If the array is already sorted, return (-1, -1) or null to indicate no sorting is needed.

Examples for Variant 1:

1
2
3

Input: nums = [2,6,4,8,10,9,15]
Output: (1, 5)
Explanation: Need to sort subarray from index 1 to 5: [6, 4, 8, 10, 9]

1
2
3

Input: nums = [1,2,3,4]
Output: (-1, -1)
Explanation: Array is already sorted

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

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
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

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
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

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
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;
	}
}

Solution for Variant 1 - Return Bounds

For the variant that returns the actual bounds instead of the length, we use the same core algorithm but modify the return value.

Method 1 - Greedy (Return Bounds)

Intuition

Same as the main problem - we find the boundaries of the unsorted subarray by tracking maximum from left and minimum from right. The only difference is we return the actual indices instead of the length.

Approach

  1. Use the same two-pass approach as Method 2 above
  2. Find left and right boundaries of the unsorted window
  3. Return (left, right) if unsorted window exists, otherwise return (-1, -1)

Code

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

class Solution {
public:
    pair<int, int> findUnsortedSubarrayBounds(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 {-1, -1};
        return {left, right};
    }
};
 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
26
27
28

func findUnsortedSubarrayBounds(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 []int{-1, -1}
    }
    return []int{left, right}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] findUnsortedSubarrayBounds(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 new int[]{-1, -1};
        return new int[]{left, right};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun findUnsortedSubarrayBounds(nums: IntArray): IntArray {
        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 intArrayOf(-1, -1)
        return intArrayOf(left, right)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def findUnsortedSubarrayBounds(self, nums: List[int]) -> Tuple[int, int]:
        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 (-1, -1)
        return (left, right)
 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
26
27
28

impl Solution {
    pub fn find_unsorted_subarray_bounds(nums: Vec<i32>) -> Vec<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 vec![-1, -1];
        }
        vec![left as i32, right as i32]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    findUnsortedSubarrayBounds(nums: number[]): [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 [-1, -1];
        return [left, right];
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass from both ends, same as the main solution
  • 🧺 Space complexity: O(1) — Only variables for boundaries and min/max, same as the main solution