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: 0
Example 3:
Input: nums = [1] Output: 0
Constraints:
1 <= nums.length <= 104-105 <= nums[i] <= 105Follow up: Can you solve it in
O(n) time complexity?We can sort a copy of the array and compare it with the original array to determine the boundaries of the subarray that needs to be sorted.
Sort the array and compare with the original array from the start and end to find the first and last mismatch. These mismatches will give the boundaries of the subarray.
The function makes a copy of the array, sorts it, and then compares it with the original array. It finds the first and last indices where the two arrays differ. If such indices are found, the length of the subarray is returned; otherwise, it's zero.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing a copy of the array.
In this approach, we aim to find the shortest unsorted subarray by utilizing two passes to find the minimum and maximum deviations from the sorted order.
The range between these two boundaries produces the result.
The idea is to use two scans of the array to find maximum and minimum deviation points. The logic helps in computing boundaries by tracking the range that is unsorted and quickly determines the shortest unsorted subarray.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) as it processes the array twice.
Space Complexity: O(1) since no additional space is used apart from basic variables.
| Approach | Complexity |
|---|---|
| Using Sorting to Identify Subarray | Time Complexity: O(n log n) due to sorting. |
| Single Pass Scan for Minimum and Maximum Deviations | Time Complexity: O(n) as it processes the array twice. |
LeetCode 581. Shortest Unsorted Continuous Subarray (Algorithm Explained) • Nick White • 19,331 views views
Watch 9 more video solutions →Practice Shortest Unsorted Continuous Subarray with our built-in code editor and test cases.
Practice on FleetCode