Leetcode 581. Shortest Unsorted Continuous Subarray
Problem Explanation
The problem asks to find the shortest subarray in a given array that if sorted, the whole array will be sorted.
For example with the array [2, 6, 4, 8, 10, 9, 15], we have to sort the subarray [6, 4, 8, 10, 9] to get [2, 4, 6, 8, 9, 10, 15] which is in ascending order. Therefore, the answer is 5 (length of the subarray).
Approach
The approach to solve this problem is to traverse the given array twice, once from left to right and once from right to left.
During the first traversal, we update the minimum element seen so far whenever we observe a decreasing sequence. During the second traversal, we update the maximum element seen so far whenever we observe an increasing sequence.
Finally, we find the first and last position in the array where the numbers are not in correct position (by comparing the numbers with the minimum and maximum elements found). The subarray between these two positions is the required shortest subarray to be sorted.
Solution
Python
1 2python 3class Solution: 4 def findUnsortedSubarray(self, nums: List[int]) -> int: 5 min_number, max_number = float('inf'), float('-inf') 6 for i in range(1, len(nums)): 7 if nums[i] < nums[i - 1]: 8 min_number = min(min_number, nums[i]) 9 max_number = max(max_number, nums[i - 1]) 10 for i in range(len(nums) - 2, -1, -1): 11 if nums[i] > nums[i + 1]: 12 min_number = min(min_number, nums[i]) 13 max_number = max(max_number, nums[i + 1]) 14 left, right = 0, len(nums) - 1 15 while left < len(nums) and nums[left] <= min_number: 16 left += 1 17 while right >= 0 and nums[right] >= max_number: 18 right -= 1 19 return max(0, right - left + 1)
Java
1 2java 3class Solution { 4 public int findUnsortedSubarray(int[] nums) { 5 int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; 6 boolean flag = false; 7 for (int i = 1; i < nums.length; i++) { 8 if (nums[i] < nums[i - 1]) 9 flag = true; 10 if (flag) 11 min = Math.min(min, nums[i]); 12 } 13 flag = false; 14 for (int i = nums.length - 2; i >= 0; i--) { 15 if (nums[i] > nums[i + 1]) 16 flag = true; 17 if (flag) 18 max = Math.max(max, nums[i]); 19 } 20 int l, r; 21 for (l = 0; l < nums.length; l++) { 22 if (min < nums[l]) 23 break; 24 } 25 for (r = nums.length - 1; r >= 0; r--) { 26 if (max > nums[r]) 27 break; 28 } 29 if (r - l < 0) 30 return 0; 31 return r - l + 1; 32 } 33}
C++
1 2cpp 3class Solution { 4public: 5 int findUnsortedSubarray(vector<int>& nums) { 6 int mini = INT_MAX; 7 int maxi = INT_MIN; 8 bool meetDecrease = false; 9 bool meetIncrease = false; 10 11 for (int i = 1; i < nums.size(); ++i) { 12 if (nums[i] < nums[i - 1]) 13 meetDecrease = true; 14 if (meetDecrease) 15 mini = min(mini, nums[i]); 16 } 17 18 for (int i = nums.size() - 2; i >= 0; --i) { 19 if (nums[i] > nums[i + 1]) 20 meetIncrease = true; 21 if (meetIncrease) 22 maxi = max(maxi, nums[i]); 23 } 24 25 int l; 26 for (l = 0; l < nums.size(); ++l) 27 if (nums[l] > mini) 28 break; 29 30 int r; 31 for (r = nums.size() - 1; r >= 0; --r) 32 if (nums[r] < maxi) 33 break; 34 35 return l < r ? r - l + 1 : 0; 36 } 37};
C#
1 2csharp 3public class Solution { 4 public int FindUnsortedSubarray(int[] nums) { 5 int min = int.MaxValue, max = int.MinValue; 6 bool flag = false; 7 for (int i = 1; i < nums.Length; i++) { 8 if (nums[i] < nums[i - 1]) 9 flag = true; 10 if (flag) 11 min = Math.Min(min, nums[i]); 12 } 13 flag = false; 14 for (int i = nums.Length - 2; i >= 0; i--) { 15 if (nums[i] > nums[i + 1]) 16 flag = true; 17 if (flag) 18 max = Math.Max(max, nums[i]); 19 } 20 int l, r; 21 for (l = 0; l < nums.Length; l++) { 22 if (min < nums[l]) 23 break; 24 } 25 for (r = nums.Length - 1; r >= 0; r--) { 26 if (max > nums[r]) 27 break; 28 } 29 if (r - l < 0) 30 return 0; 31 return r - l + 1; 32 } 33}
Javascript
1 2javascript 3var findUnsortedSubarray = function(nums) { 4 let min = Infinity, max = -Infinity; 5 let flag = false; 6 for (let i = 1; i < nums.length; i++) { 7 if (nums[i] < nums[i - 1]) 8 flag = true; 9 if (flag) 10 min = Math.min(min, nums[i]); 11 } 12 flag = false; 13 for (let i = nums.length - 2; i >= 0; i--) { 14 if (nums[i] > nums[i + 1]) 15 flag = true; 16 if (flag) 17 max = Math.max(max, nums[i]); 18 } 19 let l, r; 20 for (l = 0; l < nums.length; l++) { 21 if (min < nums[l]) 22 break; 23 } 24 for (r = nums.length - 1; r >= 0; r--) { 25 if (max > nums[r]) 26 break; 27 } 28 if (r - l < 0) 29 return 0; 30 return r - l + 1; 31};
This approach iterates over the array twice, once forward and once backward, while updating the minimum and maximum values seen so far. Lastly using this minimum and maximum values we find the first and last out-of-place elements, which marks the boundary of the subarray we want to sort.
The reason why this works is because if a number is smaller than the maximum number seen so far, it must be included in the subarray that needs to be sorted in order to make the complete array sorted. Same goes for the left boundary.
Let's simplify this with an example: [2, 6, 4, 8, 10, 9, 15]
- When we iterate over this array from the right, the maximum value seen is continuously updated until we reach the first number smaller than max, marking the right boundary of the subarray.
- The same process is repeated from the left, with the only difference of updating min and checking if the current number is greater than min, marking the left boundary of the subarray.
This solution only needs to run two passes over the array, so the time complexity is O(n), where n is the length of the array. The space complexity of this solution is O(1), because no extra data structure is used.
In conclusion, sorting the shortest subarray can be achieved by performing two traversal of the array, finding the minimum and maximum encountered so far, and then determining the first and last out-of-place positions in the array corresponding to these min and max values.
Remember: In this specific problem, decreasing (from left to right) and increasing (from right to left) sequences indicate wrongly positioned elements that should be included in our to-be-sorted subarray. These elements are the ones that dictate the start-end indexes of the subarray in the original array. The algorithm has been implemented above in Python, Java, Javascript, C++ and C# programming languages.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.