132 Pattern — Monotonic Stack with Reverse Traversal (LeetCode 456)

The 132 Pattern (LeetCode 456) asks whether an array contains three elements nums[i] < nums[k] < nums[j] with i < j < k. The naming comes from the relative ordering: the first is smallest (1), the third is middle (2), and the second is largest (3). Solving it in O(n) requires a clever stack trick.

The Problem

Given an array of n integers, return True if there exist indices i < j < k such that nums[i] < nums[k] < nums[j].

[3, 1, 4, 2] → True  (1 < 2 < 4, at indices 1,2,3)
[1, 2, 3, 4] → False (no such triple)
[-1, 3, 2, 0] → True (-1 < 2 < 3, at indices 0,1,2)
[3, 5, 0, 3, 4] → True (0 < 3 < 5 or 0 < 4 < 5)

Why Is This Hard?

The challenge is that the three elements play different roles:

• nums[i] = the “1” (smallest, leftmost)
• nums[j] = the “3” (largest, in the middle)
• nums[k] = the “2” (middle value, rightmost)

A brute-force O(n^3) check is too slow. Even an O(n^2) approach with prefix minimums is not ideal. We want O(n).

Brute Force — O(n^3)

def find132pattern_brute(nums):
    """Check all triples — O(n^3)."""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] < nums[k] < nums[j]:
                    return True
    return False

Better: Prefix Min — O(n^2)

def find132pattern_prefix(nums):
    """
    Use prefix min for s1, then scan for s2 > s1.
    O(n^2) time.
    """
    n = len(nums)
    if n < 3:
        return False

    min_i = [0] * n
    min_i[0] = nums[0]
    for i in range(1, n):
        min_i[i] = min(min_i[i - 1], nums[i])

    for j in range(1, n):
        for k in range(j + 1, n):
            if min_i[j] < nums[k] < nums[j]:
                return True
    return False

Optimal: Stack — O(n)

The key insight is to scan right to left and use a stack to track candidates for the “3” (the largest value, nums[j]). As we pop elements from the stack, we track the largest popped value — this becomes our candidate for “2” (nums[k], called s2).

If any element we encounter is less than s2, we have found the “1” and the pattern exists.

The Algorithm

1. Initialize s2 = -infinity (the “2” candidate, middle value)
2. Maintain a stack of “3” candidates (decreasing order)
3. Scan from right to left:
   • If nums[i] < s2, return True (found the “1”)
   • Pop all stack elements smaller than nums[i] — update s2 to the largest popped value
   • Push nums[i] onto the stack

def find132pattern(nums):
    """
    Monotonic stack scanning right to left.
    Time: O(n) — each element pushed/popped at most once.
    Space: O(n) — for the stack.
    """
    n = len(nums)
    if n < 3:
        return False

    stack = []  # candidates for s3 (the "3", the largest)
    s2 = float('-inf')  # best candidate for s2 (the "2", middle value)

    for i in range(n - 1, -1, -1):
        # If current element is less than s2, we found s1
        if nums[i] < s2:
            return True

        # Pop elements smaller than current — they become s2 candidates
        while stack and stack[-1] < nums[i]:
            s2 = stack.pop()  # largest popped = best s2

        stack.append(nums[i])

    return False

Detailed Trace

Example 1: [3, 1, 4, 2]

Scan right to left:

i=3, nums[i]=2:
  2 < s2(-inf)? No
  stack empty, push 2           stack=[2], s2=-inf

i=2, nums[i]=4:
  4 < s2(-inf)? No
  stack top 2 < 4 → pop, s2=2  stack=[], s2=2
  push 4                        stack=[4], s2=2

i=1, nums[i]=1:
  1 < s2(2)? YES → return True ✓

Pattern: 1 < 2 < 4 (indices 1, 2, 3)

Example 2: [1, 2, 3, 4]

i=3, nums[i]=4: push            stack=[4], s2=-inf
i=2, nums[i]=3: 3 < -inf? No.
                 3 < 4, no pop. push  stack=[4,3], s2=-inf
i=1, nums[i]=2: 2 < -inf? No.
                 2 < 3, no pop. push  stack=[4,3,2], s2=-inf
i=0, nums[i]=1: 1 < -inf? No.
                 1 < 2, no pop. push  stack=[4,3,2,1], s2=-inf

return False ✓ (strictly increasing — no 132 pattern)

Example 3: [-1, 3, 2, 0]

i=3, nums[i]=0: push             stack=[0], s2=-inf
i=2, nums[i]=2: pop 0, s2=0.
                 push 2           stack=[2], s2=0
i=1, nums[i]=3: pop 2, s2=2.
                 push 3           stack=[3], s2=2
i=0, nums[i]=-1:
  -1 < s2(2)? YES → return True ✓

Pattern: -1 < 2 < 3 (indices 0, 1, 2)

Why Does This Work?

Let us reason about the invariants:

• Stack holds values in decreasing order (monotonic decreasing). These are candidates for the “3” — the largest element.
• s2 is the largest value ever popped from the stack. When we pop x because nums[i] > x, that means nums[i] is a better “3” and x becomes a candidate for “2”. Since x was popped by something larger, s2 < some stack element is guaranteed.
• If we later find nums[i] < s2, then nums[i] is the “1”, s2 is the “2”, and the element that caused s2 to be popped is the “3”.

The indices are correct because we scan right to left: the “1” is leftmost, the “3” (which pushed out s2) comes later, and “2” (s2) comes even later.

Edge Cases

1. Array too short — length < 3 → always False
2. All equal — [5, 5, 5] → False (need strict inequalities)
3. Strictly increasing — [1, 2, 3, 4] → False
4. Strictly decreasing — [4, 3, 2, 1] → False
5. Negative numbers — handled naturally
6. Pattern at the very end — [1, 1, 1, 3, 2] → True

Complexity Analysis

Approach	Time	Space
Brute force	O(n^3)	O(1)
Prefix min	O(n^2)	O(n)
Stack	O(n)	O(n)

When to Use This Pattern

Use this reverse-traversal stack technique when:

• You need to find a specific ordering pattern in an array
• The pattern involves a “largest in the middle” structure
• You need to track the best second-choice (the popped values)
• Scanning from right to left gives you information about what comes after

Related Problems

Problem	Difficulty	Key Idea
LeetCode 456 — 132 Pattern	Medium	This problem
LeetCode 503 — Next Greater Element II	Medium	Monotonic stack
LeetCode 334 — Increasing Triplet Subsequence	Medium	Similar triple search
LeetCode 42 — Trapping Rain Water	Hard	Stack with bounded regions

Key Takeaway

The 132 Pattern is solved by scanning right to left and using a monotonic stack to track the “3” candidates. The key variable is s2 — the largest value popped from the stack — which serves as the “2” in the pattern. If any future element is less than s2, the pattern exists. This technique of tracking “the best thing that got displaced” is powerful and reusable.