Java, C++, O(n) Time O(1) Space


  • 0
    T

    1, Define two indices left and right, left is first N[i] > N[i+1] (start from 0) and right is first N[i-1] > N[i] (from length-1).
    2, Find min and max from left to right.
    3, Expand left so that N[left] < min and expand right so that N[right] > max.

    Java

        public int findUnsortedSubarray(int[] nums) {
            int left = nums.length-1, right = 0;
            for(int i = 0; i < nums.length-1; i++){
                if(nums[i] > nums[i+1]){
                    left = i;
                    break;
                }
            }
            for(int i = nums.length-1; i > 0; i--){
                if(nums[i] < nums[i-1]){
                    right = i;
                    break;
                }
            }
    
            // No change.
            if(left >= right)
                return 0;
            
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for(int i = left; i <= right; i++){
                min = Math.min(nums[i], min);
                max = Math.max(nums[i], max);
            }
            // expand left and right
            while(left >= 0 && nums[left] > min)
                left--;
            while(right < nums.length && nums[right] < max)
                right++;
                
            return right-left-1;
        }
    

    C++

        int findUnsortedSubarray(vector<int>& nums) {
            int left = nums.size()-1, right = 0;
            for(int i = 0; i < nums.size()-1; ++i)
            {
                if(nums[i] > nums[i+1])
                {
                    left = i;
                    break;
                }
            }
            for(int i = nums.size()-1; i > 0; --i)
            {
                if(nums[i] < nums[i-1])
                {
                    right = i;
                    break;
                }
            }
            if(left >= right)
                return 0;
            int minVal = INT_MAX, maxVal = INT_MIN;
            for(int i = left; i <= right; ++i)
            {
                minVal = min(minVal, nums[i]);
                maxVal = max(maxVal, nums[i]);
            }
            while(left >= 0 && nums[left] > minVal)
                left--;
            while(right < nums.size() && nums[right] < maxVal)
                right++;
            return right-left-1;
        }
    

Log in to reply
 

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