456. 132 Pattern!

class Solution {
    public boolean find132pattern(int[] nums) {
        // O(n) solution: use array and right part of the array as stack
        // record the min number from index [0, j]
        int[] memo1 = new int[nums.length];
        memo1[0] = nums[0];
        for (int i=1; i<memo1.length; i++){
            memo1[i]=Math.min(memo1[i-1], nums[i]);    
        }
        
        // use the right part of the memo1 as stack
        // for j>=stackTop and j<nums.length-1,
        // memo[j]<=memo[j+1]
        for (int j = nums.length-1, stackTop = nums.length; j>0; j--){
            while(stackTop<nums.length && memo1[stackTop]<=memo1[j]){
                stackTop++;
            }
            if(nums[j]>memo1[j] && stackTop<nums.length && memo1[stackTop]<nums[j])
                return true;
            if(nums[j]>memo1[j]) memo1[--stackTop]=nums[j];            
        }
        return false;
    }
}

class Solution {
    public boolean find132pattern(int[] nums) {
        // n solution: two pass, array and stack
        // record the min number from index [0, j]
        int[] memo1 = new int[nums.length];
        memo1[0] = nums[0];
        for (int i=1; i<memo1.length; i++){
            memo1[i]=Math.min(memo1[i-1], nums[i]);    
        }
        // memo2 is a sorted collection, 
        // that stores the numbers greater than memo1[j]
        Deque<Integer> memo2 = new LinkedList<>();
        for (int j = nums.length-1; j>0; j--){
            // if keep the elements that are smaller than memo1[j]
            // then the collection will not be ordered
            while(memo2.size()>0 && memo2.peek()<=memo1[j]){
                memo2.pop();
            }
            if(nums[j]>memo1[j]){
                if(memo2.size()>0 && memo2.peek()<nums[j]) return true;
                else memo2.push(nums[j]);
            }
        }
        return false;
    }
}

class Solution {
    public boolean find132pattern(int[] nums) {
        // n2 solution: track the min value before j
        int min = nums[0];
        for(int i=1; i<nums.length; i++){
            if(min<nums[i]){
                for(int j=i+1; j<nums.length;j++){
                    if(nums[j]<nums[i] && nums[j]>min) return true;
                }
            }
            min=Math.min(min, nums[i]);
        }
        return false;
    }
}