Shortest Unsorted Continous Subarray


  • 0

    Click here to see the full article post


  • 0
    A

    Approach #3 uses O(n) space, since you're make a copy of the original array.


  • 0

    @arpit32 I have corrected it. Thanks.


  • 0
    W

    Another approach. If we find the leftmost violation and rightmost violations first, we could construct the continuous subarray start from here. Let's say the leftmost violation is "left" and rightmost violation is "right", we could find the minimum and maximum of subarray A[left + 1, right - 1] in linear time O(right - left - 1). If the minimum is larger than A[left] and maximum is smaller than A[right], we are done, we just return "right - left - 1". Otherwise, if minimum is smaller than A[left], we set left -- and update maximum value. Similarly, if maximum is larger than A[right], we set right ++ and update minimum value. Since "left" and "right" are bounded. The total operations is O(n).
    If left reached outside the boundary and right reached outside the boundary, we return the total length of the array.

    The time complexity is O(n)
    Space complexity is O(1)

    Below is the code implementation.

    public int findUnsortedSubarray(int[] nums) {

        int i, j, k, left, right;
        i = 0;
        j = nums.length - 1;
        for(i = 0; i < nums.length - 1; i ++) {
            if(nums[i] <= nums[i + 1]) continue; // find left violation
            else break;
        }
        if(i == nums.length - 1) return 0;
        left = i;
        for(j = nums.length - 1; j >= 1; j --) {
            if(nums[j] >= nums[j - 1]) continue; // find right violation
            else break;
        }
        if (j == 0) return 0;
        right = j;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(k = left + 1; k <= right - 1; k ++) {
            min = Math.min(min, nums[k]);
            max = Math.max(max, nums[k]);
        }
        if(left + 1 > right - 1) {
            max = nums[left];
            min = nums[right];
        }
        while (left >= 0 && right < nums.length) {
            if (nums[left] > min) {
                max = Math.max(max, nums[left]);
                left --;
            }
            else {
                if (nums[right] < max) {
                min = Math.min(min, nums[right]);
                right ++;
                }
                else {
                    return (right - left - 1);
                }
            }
        }
        if(left == - 1) {
            while(right < nums.length) {
                if (nums[right] < max) {
                min = Math.min(min, nums[right]);
                right ++;
                }
                else {
                    return (right - left - 1);
                }
            }
        }
        if(right == nums.length) {
            while(left >= 0) {
                if (nums[left] > min) {
                max = Math.max(max, nums[left]);
                left --;
                }
                else {
                    return (right - left - 1);
                }
            }
        }
        return nums.length;
    }
    

    """


  • 0
    Y

    The purpose is to find the index of local minimum and local maximum but not global ones, the explanation is kind of confusing.


  • 0
    G

    about approch 3 . we also can find the unsorted array has surely started ,i, and ended ,j, first,then we find the max and min between started and ended,the compared with sorted array, find the final required boundary .


  • 0
    J

    flag variable is not needed in the last solution. can remove that


  • 0
    G

    class Solution {
    public int findUnsortedSubarray(int[] nums) {
    int left=-1,right=0;
    for(int i = 0;i<nums.length-1;i++){
    if(nums[i+1] < nums[i]){
    if(left == -1) left = i;
    right = i+1;
    }
    }
    return right==0?0:right-left+1;
    }
    }


  • 0
    D

    Time complexity: O(n). Three O(n) loops are used.

    Space complexity: O(1) Constant space is used.

    ACCEPTED Solution:

    public int findUnsortedSubarray(int[] nums) {
    	int n=nums.length;
    	Boolean mxflag=false, mnflag=false;
    	int maxkinkai=0,maxkinkoi=0, minkinkai=0, minkinkoi=0, minval=0, maxval=0;
    	for(int i=0; i<n; i++){
    		Boolean lflag=false, rflag=false,leflag=false, reflag=false;
    		if(i-1>=0 && nums[i-1] > nums[i])
    			lflag=true;
    		if(i-1>=0 && (i!=n-1 && nums[i-1] == nums[i]))
    			leflag=true;
    		if(i+1>=n || nums[i+1]>nums[i])
    			rflag=true;
    		if(i+1>=n || nums[i+1]==nums[i])
    			reflag=true;    		
    		if((lflag && rflag) || (lflag && reflag) || (leflag && rflag) ){
    			if(mnflag){
    				if(nums[i] <= minval){
    					minval=nums[i];
    					minkinkai=i;
    				}
    			}
    			else{
    				minval=nums[i];
    				minkinkai=i;
    				mnflag=true;
    			}
    		}
    		lflag=false;leflag=false;
    		rflag=false; reflag=false;
    
    		if(i-1 < 0 || nums[i-1] < nums[i])
    			lflag=true;
    		if(i-1 < 0 || nums[i-1] == nums[i])
    			lflag=true;    		
    		if(i+1<n && nums[i+1] < nums[i])
    			rflag=true;
    		if(i+1<n && (i!=0 && nums[i+1] == nums[i]))
    			reflag=true;    		
    		
    		if(lflag && rflag){
    			if(mxflag){
    				if(nums[i] > maxval){
    					maxval=nums[i];
    					maxkinkai=i;
    				}
    			}
    			else{
    				maxval=nums[i];
    				maxkinkai=i;
    				mxflag=true;
    			}
    		}
    		
    	}
    	
    	
    	if(mnflag){
    		for(int i=0; i<minkinkai;i++){
    			if(nums[i]> minval){
    				minkinkoi=i;
    				break;
    			}
    		}
    	}
    	
    
    	if(mxflag){
    		for(int i=n-1; i>maxkinkai;i--){
    			if(nums[i]< maxval){
    				maxkinkoi=i;
    				break;
    			}
    		}
    	}
    
    	
    	if(mnflag && mxflag)
    		return Math.max(minkinkai, maxkinkoi) - Math.min(minkinkoi, maxkinkai)+1;
    	else if(mnflag && !mxflag)
    		return minkinkai - minkinkoi+1;
    	else if(!mnflag && mxflag)
    		return maxkinkoi - maxkinkai+1;
    	if(!mnflag && !mxflag)
    		return 0;    	
    	
    	
    	return 0;
    }

  • 0
    J
        int findUnsortedSubarray(vector<int>& nums) {
            int M = nums[0];
            int beg = -1;
            int end = -1;
            int minReverseIndex = -1;
            for (int i = 1; i < nums.size(); i++) {
                if (nums[i] < M) {
                    end = i;
                    if (minReverseIndex < 0 || nums[i] < nums[minReverseIndex]) {
                        minReverseIndex = i;
                    }
                }
                else {
                    M = nums[i];
                }
            }
                
            for (int i = 0; i < minReverseIndex; i++) {
                if (nums[i] > nums[minReverseIndex]) {
                    beg = i;
                    break;
                }
            }
                
            return beg < 0 ? 0 : end - beg + 1;
        }
    

  • 0
    A

    The idea is to find the start position and end position of the sub array by traversing while noting down the index of the violation (i.e., smaller number after the big number). Whenever the violation is made, we need to make sure that the small number is really the small number so far. For this, we would have to traverse the elements that have been scanned so far. If there is any smaller number than the current index location, then set the start of the sub array as that of the smaller number index.

        int findUnsortedSubarray(vector<int>& nums) {
            // If list is empty or of size 1, then function returns 0.
            int saStartIndex = -1;
            int saLength = 0;
            int bigNumIndex = 0;
            for(int i=1; i < nums.size(); i++){
                if(nums[i] < nums[bigNumIndex]){
                    if( saStartIndex == -1 || nums[saStartIndex] > nums[i] ){
                        for(int saIndex=0; saIndex<i; saIndex++){
                            if(nums[saIndex] > nums[i]){
                                saStartIndex = saIndex;
                                break;
                            }
                        }
                    }
                    saLength = i - saStartIndex + 1;                    
                }
                else{ // If greater (or equal to), then update the new bigger number.
                    bigNumIndex = i;
                }
            }
            return saLength;
        }
    

    Complexity Analysis

    • Time complexity : O(n log n). O(n) for traversing the array i.e., outer loop, and O(log n) to find the starting point of sub-array i.e., inner for loop which traverses from index 0 till current position i.
    • Space complexity : O(1). Constant space is used.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.