February LeetCoding Challenge 2021
Day 25
Shortest Unsorted Continuous Subarray
PROBLEM STATEMENT:
Given an integer array
Example 1
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.
strong>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
O(n)
time complexity? Explanation
ALGORITHM:
- Maintain a stack.
- Traverse the array from left to right.
- If current element is greater than previous element (rising slope), push the index in the array.
- Else pop the elements of stack until the element(corresponding to the index) on the top of the stack is less than the current element.If the popping stops with when stacks top is k, the current element’s correct position in k+1.
- We follow the same process while traversing over the whole array, and determine the value of minimum such k. This marks the left boundary of the unsorted subarray..
- Similarly, to find the right boundary of the unsorted subarray, we traverse over the numsnums array backwards.This time we keep on pushing the elements if we see a falling slope.
- Time complexity : O(n)
- Space complexity : O(n)
code
C++
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
stack<int> st;
int l = nums.size();
int r = 0;
for(int i=0;i<nums.size();++i){
while(!st.empty() && nums[st.top()] > nums[i])
{
l = min(l,st.top());
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
for(int i=nums.size()-1;i>=0;--i){
while(!st.empty() && nums[st.top()] < nums[i])
{
r = max(r,st.top());
st.pop();
}
st.push(i);
}
return r-l > 0 ? r-l+1 : 0;
}
};
PYTHON
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
st = []
l = len(nums)
r = 0
for i in range(len(nums)):
while len(st) and nums[st[-1]]>nums[i]:
l = min(l,st[-1])
st.pop()
st.append(i)
st.clear()
for i in range(len(nums)-1,-1,-1):
while len(st) and nums[st[-1]] < nums[i]:
r = max(r,st[-1])
st.pop()
st.append(i)
return r-l+1 if r-l>0 else 0