Shortest Unsorted Continuous Subarray LeetCode Solution

Table of Contents

Problem Statement

Shortest Unsorted Continuous Subarray LeetCode Solution says that – Given an integer array nums, you have 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 length of the shortest subarray.

Example 1:

Input:

 nums = [2,6,4,8,10,9,15]

Output:

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:

ALGORITHM

In order to find Shortest Unsorted Continuous Subarray. First, we will find the unsorted order from the left side of the array and also from the right side of the array. After finding the index from both sides at last we will return right-left+1.

APPROACH

At first, we will make two variables maxi and mini in which mini-stores the mini value of the unsorted array from the left side, and maxi stores the maximum value of unsorted array from the right side.
after we will iterate from left to right in an array and find the minimum value from the unsorted order and again iterate from right to left in order to find the maximum value from the unsorted order.
Then will check if minimum == MIN_Value and maximum == MAX_Value simply return 0(because the array is already in sorted order).
Then again iterate from left to right and if we find a value greater than mini then simply break the loop and the same in case of the right to left if we find the value smaller than maxi then simply break the loop and at last will return the (end-start+1).
Hence Shortest Unsorted Continuous Subarray will be calculated.

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        
        int maxi = Integer.MIN_VALUE;
        int mini = Integer.MAX_VALUE;
        
        for(int i=1;i<nums.length;i++){
            if(nums[i] < nums[i-1]){
                if(mini > nums[i])
                    mini = nums[i];
                   
            }
            
        }
        
        for(int i = nums.length-2;i >= 0;i--){
            
            if(nums[i] > nums[i+1]){
                
                if(maxi < nums[i])
                    maxi = nums[i];
                
                
            }
        }
        
        if(mini == Integer.MAX_VALUE && maxi == Integer.MIN_VALUE)
            return 0;
        
        
        
        int start = 0;
        int end = nums.length;
        
        for(start = 0;start < nums.length;start++){
            
            if(mini < nums[start])
                break;
            
        }
        
        for(end = nums.length-1;end >= 0;end--){
            
            if(maxi > nums[end])
                break;
            
        }
        
        
        return (end-start+1);
        
        
    }
}

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        
        maxi = -9999999
        mini = 9999999
        
        for i in range(1,len(nums)):
            if nums[i] < nums[i-1]:
                mini = min(nums[i],mini)
                
        
        for i in range(len(nums)-2,-1,-1):
            if nums[i] > nums[i+1]:
                maxi = max(nums[i],maxi)
                
        
        if mini == 9999999 and maxi == -9999999:
            return 0
        
        for start in range(len(nums)):
            if nums[start] > mini:
                break
                
        for end in range(len(nums)-1,-1,-1):
            if nums[end] < maxi:
                break
                
        return end-start+1

Complexity Analysis of Shortest Unsorted Continuous Subarray Leetcode Solution:

Time Complexity:

The Time Complexity of the above Solution is O(N) since accessing each index at most one time.

Space Complexity:

The Space Complexity of the above Solution is O(1) since we are using constant extra space in the above solution.