Java Time O(N) Space O(N)


  • 0
    C

    To find the begin, we need find the first number that less than the minimum at the right side of the array. How to know the minimum? To scan the array from right to left, mark minimum value till each position, for example:
    [5, 7, 6, 9], scan from 9 to 5, and create the minimum array:
    [9]
    [6, 9]
    [6, 6, 9]
    [5, 6, 6, 9]
    now check origin array from left to right, you will find out the second number 7 is problem, as that position minimum is 6.

    same thing you will find the end

    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int len = nums.length;
            int[] left = new int[len];
            int[] right = new int[len];
            
            left[0] = nums[0];
            for(int i=1; i< len; i++) {
                left[i] = Math.max(left[i-1], nums[i]);
            }
            
            right[len-1] = nums[len-1];
            for(int i=len-2; i>=0; i--) {
                right[i] = Math.min(right[i+1], nums[i]);
            }
            
            int a = -1;
            for(int i=0; i< len; i++) {
                if(nums[i] > right[i]) {
                    a = i;
                    break;
                }
            }
            
            int b = -1;
            for(int i=len-1; i>=0; i--) {
                if(nums[i] < left[i]) {
                    b = i;
                    break;
                }
            }  
            
            if( a == -1 || b == -1) return 0;
            
            return b - a + 1;
        }
    }
    

Log in to reply
 

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