132 Pattern

medium array stack monotonic stack

Problem

Given nums, return true if it contains a 132 pattern: indices i < j < k with nums[i] < nums[k] < nums[j].

Inputnums = [3, 1, 4, 2]

Outputtrue

i=1 (1), j=2 (4), k=3 (2): 1 < 2 < 4. ✓

nums (comma-separated)

def find132pattern(nums):
    stack = []
    s2 = float('-inf')   # best candidate for '2'
    for x in reversed(nums):
        if x < s2: return True
        while stack and stack[-1] < x:
            s2 = max(s2, stack.pop())
        stack.append(x)
    return False

function find132pattern(nums) {
  const stack = [];
  let s2 = -Infinity;
  for (let i = nums.length - 1; i >= 0; i--) {
    const x = nums[i];
    if (x < s2) return true;
    while (stack.length && stack[stack.length - 1] < x) {
      s2 = Math.max(s2, stack.pop());
    }
    stack.push(x);
  }
  return false;
}

class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int s2 = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            int x = nums[i];
            if (x < s2) return true;
            while (!stack.isEmpty() && stack.peek() < x) {
                s2 = Math.max(s2, stack.pop());
            }
            stack.push(x);
        }
        return false;
    }
}

bool find132pattern(vector<int>& nums) {
    stack<int> st;
    int s2 = INT_MIN;
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        int x = nums[i];
        if (x < s2) return true;
        while (!st.empty() && st.top() < x) {
            s2 = max(s2, st.top()); st.pop();
        }
        st.push(x);
    }
    return false;
}

Explanation

A 132 pattern needs three numbers in order where the first is the smallest, the middle is the largest, and the last sits in between. The clever trick is to scan the array right-to-left and keep track of the best possible "2" we have seen so far.

We use a stack to hold candidates for the big "3", and a variable s2 for the largest valid "2" so far (something that was once a "3" but then got beaten by an even bigger number to its right).

For each number x going right-to-left: if x < s2, then x can play the role of the small "1" and we have found the pattern, so return true. Otherwise, while the stack top is smaller than x, we pop it and raise s2 to that popped value — it means x is a new "3" and the popped value is a valid "2" sitting to its right. Then push x.

Example: nums = [3, 1, 4, 2]. Scanning from the right, 2 and 4 set up s2 = 2 (since 4 > 2). When we reach 1, it is less than s2 = 2, so we have 1 < 2 < 4 and return true.

Because s2 always holds a number that had something bigger before it, finding any later value below s2 instantly completes the 1-3-2 shape in a single pass.

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