Stack O(n) Java solution with explanation


  • 0
    M

    My solution uses two pass to go over the whole array.

    For the first pass, we should go from left to right to find potential mid number "3" with their min left value "1". For example, in the array [-2,6,5,4], the first 6 (index = 1) is a potential mid number with left min as -2.

    For the second pass, we go from right to left, we want to have a stack to keep a sequence with stack peek to be the smallest number. For example, in array [-2,6,5,4], we first push 4 (index = 3), then go to 5 (index=2), at 5, we find out that it is larger than our stack peek, so it can be a potential mid number "3", then we validate if it is a real result here. If so, return true, if not, we pop out stack peek 4, then add 5 into stack. (In this example, -2,5,4 is a valid result, so we just return true without any more stack operations).

    public class Solution {
        public boolean find132pattern(int[] nums) {
            if(nums == null || nums.length == 0) {
                return false;
            }
            
            int min = Integer.MAX_VALUE;
            boolean[] three = new boolean[nums.length];
            int[] values = new int[nums.length];
            for(int i = 0; i < nums.length; i ++) {
                if(i == 0){
                    min = nums[i];
                } else if(nums[i] > min) {
                    three[i] = true;
                    values[i] = min;
                } else {
                    min = nums[i];
                }
            }
    
            Stack<Integer> stack = new Stack<>();
            for(int i = nums.length-1; i >= 0; i --) {
                if(stack.isEmpty()) {
                    stack.add(nums[i]);
                } else if(nums[i] < stack.peek()) {
                    stack.add(nums[i]);
                } else if(nums[i] > stack.peek()) {
                     while(!stack.isEmpty() && nums[i] > stack.peek()) {
                        int top = stack.peek();
                        if(top > values[i] && three[i]) {
                            return true;
                        } else if(top > nums[i]) {
                            break;
                        }
                        stack.pop();
                    }
                    if(stack.isEmpty()) {
                        stack.add(nums[i]);
                    }
                }
            }
    
            return false;
        }
    }
    

Log in to reply
 

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