132 Pattern — Monotonic Stack from Right

Problem 266 · 132 Pattern

Difficulty: Medium · Pattern: Monotonic Stack (right to left)

Find i < j < k such that nums[i] < nums[k] < nums[j].

Intuition

Scan right to left. Maintain a monotonic decreasing stack. Track k_val (the largest value popped — candidate for nums[k]). For each new element (potential nums[i]), if it's < k_val, we found the pattern.

Solutions

# Python
def find132pattern(nums):
    stack = []
    k_val = float('-inf')
    for i in range(len(nums)-1, -1, -1):
        if nums[i] < k_val: return True
        while stack and stack[-1] < nums[i]:
            k_val = stack.pop()
        stack.append(nums[i])
    return False

// Java
public boolean find132pattern(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>();
    int kVal = Integer.MIN_VALUE;
    for (int i=nums.length-1;i>=0;i--) {
        if (nums[i] < kVal) return true;
        while (!stack.isEmpty() && stack.peek() < nums[i]) kVal=stack.pop();
        stack.push(nums[i]);
    }
    return false;
}

Complexity

Time: O(n)
Space: O(n)