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 .


Log in to reply
 

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