456. 132 Pattern

naive

O(n^3)

O(1)

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

optimized naive 2

T: O(n^2)

T: O(1)

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        // goal: make index i > j > k, nums[i] < nums[k] < nums[j]
        int numi = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            numi = Math.min(nums[j], numi);
            for (int k = n-1; k > j; k--) {
                if (numi < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

mono stack

this one is kind of like next greater, but this one is to find next smaller, from end

T: O(n)

S: O(n)

class Solution {
    public boolean find132pattern(int[] nums) {
        
        // we want s1 s3 s2(middle), where s1 < s2 < s3
        Deque<Integer> stack = new ArrayDeque<>();
        int middle = Integer.MIN_VALUE;
        
        // from end to do..
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                middle = stack.pop();
            }
            if (nums[i] > middle) {
                stack.push(nums[i]);
            }
            if (nums[i] < middle) {
                return true; // means find s1
            }
        }
        return false;
    }
}

/*
such that i < j < k and nums[i] < nums[k] < nums[j].

i, k, j

s l m

1 4 2

-1 3 2

-1 3 0

3,1,4,2. ( from end, so 2 , 4, 1 => 

(from end to do)
like find next smaller, but we need hold the first one(max), but actually we pop smaller one from stack, num > stack.peek

1
4
max = 2


3
2
m = 
*/