581. Shortest Unsorted Continuous Subarray
Problem Description
In this LeetCode problem, we are given an array of integers (nums
). The task is to identify the smallest segment (continuous subarray) of this array that, if we sort it, the entire array becomes sorted in non-decreasing order (i.e., ascending order with duplicates allowed). The goal is to find the length of this smallest segment.
We are looking for the subarray where once sorted, the values before and after this selected part fit in order and don't disrupt the non-decreasing sequence. To solve this problem, we have to distinguish between the parts of the array which are already in the correct position and those that are not.
Intuition
There are different strategies that we could use to solve this problem, some being more optimal than others. The initial, more straightforward approach is to sort a copy of the array and to compare it to the original. The first and last positions where they differ will give us the boundaries of the subarray that needs to be sorted.
However, the actual implemented solution follows a more optimal and intuitive approach that avoids using extra space and reduces the time complexity. The solution involves iterating over the array while keeping track of the maximum and minimum values seen from the left and the right, respectively.
While scanning from the left, we maintain the maximum value encountered so far - let's call it mx
. If at any index i
, the value x
is less than mx
, this suggests x
is out of its required sorted position because everything before it is already part of a non-decreasing sequence. Hence, x
should be included in the subarray that needs sorting. The rightmost index r
where this occurs marks the endpoint of the unsorted subarray.
Simultaneously, we scan from the right and maintain the minimum value encountered so far - referenced as mi
. Upon finding an element greater than mi
at index n - i - 1
from the end, it indicates this element is also out of order. The leftmost index l
where this situation arises becomes the beginning of the unsorted subarray.
Initially, l
and r
are set to -1
, and if they remain unchanged after the iterations, it means the entire array is already sorted, and we return length 0
. If they have been updated, the length of the minimum subarray required to be sorted is calculated by the difference r - l + 1
.
The intuition behind updating r
and l
only when we find values out of their required position is that only these values define the boundaries of the shortest unsorted subarray—and only by sorting them can we achieve a fully sorted array.
Learn more about Stack, Greedy, Two Pointers, Sorting and Monotonic Stack patterns.
Solution Approach
The solution involves a single pass approach that cleverly makes use of two properties, namely tracking the maximum and minimum values from the left and right, respectively. By doing this, we can identify the bounds of the unsorted subarray without having to sort the array or use extra space.
Let's understand this algorithm step by step:
-
Initialize Variables: Two pointers
l
andr
are initialized to-1
which will represent the left and right bounds of the unsorted subarray. We also initialize two variables,mi
to+infinity
, representing the minimum value seen from the right; andmx
to-infinity
, representing the maximum value seen from the left. -
Iterate Over the Array: We loop over all elements in the array using a variable
i
that goes from0
ton - 1
, wheren
is the length of the array. While iterating, we perform the following:- Update Right Boundary (
r
): For thei
-th elementx
, we compare it with the maximum value seen so farmx
. Ifx
is smaller thanmx
, it meansx
is out of place and should be part of the subarray to be sorted, so we updater
to be the current indexi
. - Update Maximum (
mx
): Ifx
is greater than or equal tomx
, we updatemx
to bex
because it's the new maximum value seen so far. - At each iteration of
i
, we also consider the mirror position from the right end of the array: indexn - i - 1
. - Update Left Boundary (
l
): We comparenums[n - i - 1]
with the minimum value seen from the rightmi
. Ifnums[n - i - 1]
is bigger thanmi
, it's out of place and should be included in the subarray to be sorted, so we updatel
to ben - i - 1
. - Update Minimum (
mi
): Ifnums[n - i - 1]
is less than or equal tomi
, we updatemi
to this value because it's now the minimum seen from the right.
- Update Right Boundary (
-
Calculate the Subarray Length: After iterating through the array, we check if
r
was updated. Ifr
is not updated (r == -1
), it means the array was already sorted, and we return0
. Otherwise, we return the length of the subarray that needs to be sorted, which isr - l + 1
.
By iterating from both ends towards the center and updating l
and r
on-the-go, we are leveraging the information of where the sequence breaks from being non-decreasing. mx
and mi
act as sentinels to detect any number that doesn't fit into the non-decreasing order up to that point, thus efficiently finding the shortest unsorted window in one single pass with a time complexity of O(n)
and space complexity of O(1)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example using the described solution approach. Consider the array nums = [2, 6, 4, 8, 10, 9, 15]
.
Step 1: Initialize Variables
l = -1
r = -1
mi = +infinity
mx = -infinity
Step 2: Iterate Over the Array
- We start iterating from the first element to the last.
- For each element, we perform the checks and updates as specified.
Let's see this in action:
i. When i = 0
, element nums[i] = 2
.
mx = max(-infinity, 2) = 2
.- The mirror index from the right is
n - 0 - 1 = 6
. Elementnums[6] = 15
. mi = min(+infinity, 15) = 15
.
ii. Moving to i = 1
, nums[i] = 6
.
- Element
6
is not less thanmx (2)
. Thus,mx
becomes6
. - The mirror index from the right is
n - 1 - 1 = 5
. Elementnums[5] = 9
. mi
becomesmin(15, 9) = 9
.
iii. Next, i = 2
, nums[i] = 4
.
4
is less thanmx (6)
, hence we updater = 2
.- The mirror index from the right is
n - 2 - 1 = 4
. Elementnums[4] = 10
. mi
is now themin(9, 10) = 9
.
iv. For i = 3
, nums[i] = 8
.
8
is not less thanmx (6)
. So,mx
becomes8
.- The mirror index is
n - 3 - 1 = 3
. Elementnums[3] = 8
. mi
stays at9
since8
is less thanmi
.
v. When i = 4
, nums[i] = 10
.
10
is not less thanmx
. Updatemx
to10
.- The mirror index is
n - 4 - 1 = 2
. Elementnums[2] = 4
. 4
is less thanmi (9)
, so we updatel = 2
.
As we continue, mx
and mi
will not update any further because the remaining elements (nums[5] = 9
and nums[6] = 15
) are greater than all seen max values and less than all seen min values, respectively.
Step 3: Calculate the Subarray Length
- After completing the iteration,
l
is found to be2
andr
is also2
. - They both referred to the same element because we performed the
l
update after ther
update. - We need to find the full range of the unsorted segment.
- We already know
r
should be at least5
, becausenums[5] = 9
was out of place. - Correcting for the left boundary due to the two-pointer check in the algorithm,
l
should be1
, not2
. The elementnums[1] = 6
initiated the descending sequence. - Thus, the length of the subarray is
r - l + 1 = 5 - 1 + 1 = 5
.
The subarray [6, 4, 8, 10, 9]
from indices 1
to 5
is the smallest segment that, once sorted, the entire array nums
becomes sorted. The length of this segment is 5
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findUnsortedSubarray(self, nums: List[int]) -> int:
5 # Initializing minimum and maximum values found while traversing
6 minimum, maximum = float('inf'), float('-inf')
7
8 # Initializing the left and right boundaries of the subarray
9 left_boundary, right_boundary = -1, -1
10
11 # Length of the input list
12 length = len(nums)
13
14 # Iterate over the list to find the right boundary of the subarray
15 for i in range(length):
16 if maximum > nums[i]:
17 # Found a new right boundary if current number is less than the maximum seen so far
18 right_boundary = i
19 else:
20 # Update the maximum value seen so far
21 maximum = nums[i]
22
23 # Checking the left boundary using the mirrored index (from the end)
24 if minimum < nums[length - i - 1]:
25 # Found a new left boundary if current number is more than the minimum seen so far
26 left_boundary = length - i - 1
27 else:
28 # Update the minimum value seen so far
29 minimum = nums[length - i - 1]
30
31 # If the right boundary is still -1, the array is already sorted, hence return 0
32 # Otherwise return the length of the unsorted subarray
33 return 0 if right_boundary == -1 else right_boundary - left_boundary + 1
34
1class Solution {
2 public int findUnsortedSubarray(int[] nums) {
3 // Initialize variables
4 final int MAX_INT = Integer.MAX_VALUE; // Use MAX_VALUE constant for clarity
5 int n = nums.length; // Length of the input array
6 int leftIndex = -1, rightIndex = -1; // Track the left and right boundaries of the subarray
7 int minUnsorted = MAX_INT, maxUnsorted = Integer.MIN_VALUE; // Set initial values for min and max of the unsorted subarray
8
9 // Loop through the array to find the unsorted subarray's boundaries
10 for (int i = 0; i < n; ++i) {
11
12 // If current max is greater than the current element, it might belong to the unsorted part
13 if (maxUnsorted > nums[i]) {
14 rightIndex = i; // Update the right boundary
15 } else {
16 maxUnsorted = nums[i]; // Update the current max for the sorted part
17 }
18
19 // Simultaneously, check the unsorted subarray from the end of the array
20 if (minUnsorted < nums[n - i - 1]) {
21 leftIndex = n - i - 1; // Update the left boundary
22 } else {
23 minUnsorted = nums[n - i - 1]; // Update the current min for the sorted part
24 }
25 }
26
27 // If rightIndex is not updated, the array is fully sorted, return 0
28 // Otherwise, return the length of the subarray that must be sorted
29 return rightIndex == -1 ? 0 : rightIndex - leftIndex + 1;
30 }
31}
32
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int findUnsortedSubarray(vector<int>& nums) {
8 const int INF = 1e9; // Use uppercase for constant values
9 int n = nums.size(); // Size of the input vector
10 int left = -1, right = -1; // Initialize the left and right pointers of the subarray
11 int minVal = INF, maxVal = -INF; // Initialize the minimum and maximum values seen so far
12 for (int i = 0; i < n; ++i) {
13 // Iterate forward through the vector to find the right boundary of the unsorted subarray
14 if (maxVal > nums[i]) {
15 right = i;
16 } else {
17 maxVal = nums[i];
18 }
19 // Iterate backward through the vector to find the left boundary of the unsorted subarray
20 if (minVal < nums[n - i - 1]) {
21 left = n - i - 1;
22 } else {
23 minVal = nums[n - i - 1];
24 }
25 }
26 // If right is -1, the array is already sorted; otherwise, calculate the length of the unsorted subarray
27 return right == -1 ? 0 : right - left + 1;
28 }
29};
30
1/**
2 * Finds the length of the smallest contiguous subarray that, if sorted, results in the whole array being sorted.
3 * @param nums Array of numbers to be checked.
4 * @return The length of such subarray.
5 */
6function findUnsortedSubarray(nums: number[]): number {
7 let left = -1;
8 let right = -1;
9 let minOutOfOrder = Infinity;
10 let maxOutOfOrder = -Infinity;
11 const length = nums.length;
12
13 // Traverse the array to find the boundaries where the order is incorrect.
14 for (let i = 0; i < length; ++i) {
15 // From the left, identify the rightmost index that is out of order.
16 if (maxOutOfOrder > nums[i]) {
17 right = i;
18 } else {
19 maxOutOfOrder = nums[i];
20 }
21 // From the right, identify the leftmost index that is out of order.
22 if (minOutOfOrder < nums[length - i - 1]) {
23 left = length - i - 1;
24 } else {
25 minOutOfOrder = nums[length - i - 1];
26 }
27 }
28
29 // If no out-of-order elements are found, the array is already sorted (return 0).
30 // Otherwise, return the length of the unsorted subarray.
31 return right === -1 ? 0 : right - left + 1;
32}
33
Time and Space Complexity
The time complexity of the given code is O(n)
. This is because the code contains only one for loop that iterates over all elements of the array, nums
, exactly once. Inside the loop, it performs a constant number of operations for each element, which does not depend on the size of the array.
The space complexity of the code is O(1)
which means constant space. No additional space is utilized that is dependent on the input size n
, besides a fixed number of individual variables (mi
, mx
, l
, r
, and n
) that occupy space which does not scale with the size of the input array.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.