Java O(n) Stack Solution


  • 0
    W
        public int findUnsortedSubarray(int[] nums) {
            if (nums.length <= 1) return 0;
            
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            int left = -1;
            loop1:
            for (int i = 1; i < nums.length; i++) {
                int prev = nums[stack.peek()];
                while (!stack.isEmpty() && nums[i] < prev) {
                    left = stack.pop();
                    if (stack.isEmpty()) break loop1;
                    prev = nums[stack.peek()];
                }
                if (left == -1) stack.push(i);
            }
            if (left == -1) return 0;
            
            stack = new Stack<>();
            stack.push(nums.length - 1);
            int right = -1;
            loop2:
            for (int i = nums.length - 1; i >= left; i--) {
                int prev = nums[stack.peek()];
                while (!stack.isEmpty() && nums[i] > prev) {
                    right = stack.pop();
                    if (stack.isEmpty()) break loop2;
                    prev = nums[stack.peek()];
                }
                if (right == -1) stack.push(i);
            }
            
            return right - left + 1;
        }
    

Log in to reply
 

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