Shortest Unsorted Continuous Subarray
MedPrompt
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: 0Example 3:
Input: nums = [1]
Output: 0
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 105
Follow up: Can you solve it in
O(n) time complexity?Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves creating a sorted version of the input array and comparing it with the original array. The boundaries of the required subarray are determined by the first and last positions where the elements of the original array and the sorted array do not match.
Algorithm
- Create a clone of the input array
numsand name itsorted_nums. - Sort the
sorted_numsarray in non-decreasing order. - If
numsis identical tosorted_nums, the array is already sorted, so return 0. - Find the first index from the left,
left, wherenums[left]differs fromsorted_nums[left]. - Find the first index from the right,
right, wherenums[right]differs fromsorted_nums[right]. - The length of the shortest unsorted subarray is
right - left + 1.
Walkthrough
The most straightforward way to identify the unsorted portion of an array is to have a sorted version of it for reference. By comparing the original array nums with its sorted counterpart, we can pinpoint exactly which elements are out of place.
We start by creating a copy of nums and sorting it. Then, we iterate from both ends of the arrays inward. The first index from the left where nums[i] and sorted_nums[i] are different gives us the left boundary of the unsorted subarray. Similarly, the first mismatch from the right gives us the right boundary. If no mismatches are found, the array is already sorted, and the length is 0. Otherwise, the result is the distance between these two boundaries, inclusive.
import java.util.Arrays; class Solution { public int findUnsortedSubarray(int[] nums) { int[] sorted_nums = nums.clone(); Arrays.sort(sorted_nums); int start = nums.length, end = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != sorted_nums[i]) { start = Math.min(start, i); end = Math.max(end, i); } } if (end - start >= 0) { return end - start + 1; } else { return 0; } }}Complexity
Time
O(n log n) - The dominant operation is sorting the array, which typically takes `O(n log n)` time. The subsequent linear scans take `O(n)` time.
Space
O(n) - A copy of the input array is created for sorting, which requires space proportional to the number of elements, `n`.
Trade-offs
Pros
Simple to conceptualize and implement.
Correctly handles all edge cases, including already sorted arrays.
Cons
The time complexity is dominated by the sorting algorithm, making it slower than linear-time solutions.
Requires extra space proportional to the input array size to hold the sorted copy.
Solutions
Solution
class Solution {public int findUnsortedSubarray(int[] nums) { final int inf = 1 << 30; int n = nums.length; int l = -1, r = -1; int mi = inf, mx = -inf; for (int 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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.