Shortest Unsorted Continuous Subarray | February Leetcoding Challenge 2021 | Day 25
logo
Manas Sinha
Developer | Designer
Problems
Leetcode

By Manas | 25 February 2021

February LeetCoding Challenge 2021

Day 25

Shortest Unsorted Continuous Subarray

PROBLEM  STATEMENT:
Given an integer array 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.
Example 1 
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: 0
Example 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?

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

LEAVE A COMMENT

If you like the post leave a comment and share it.

Tags: , , , ,

Leave a Reply