Problem Statement

132 Pattern

You are given a list of numbers called nums. A "132 pattern" is three numbers, picked in left-to-right order from the list, that follow a special shape. The name "132" tells you the shape: the first number is the smallest, the third number is in the middle, and the second number is the biggest. More precisely, you need three positions i, j, k where i comes before j, and j comes before k, and the values fit nums[i] < nums[k] < nums[j]. So the middle position holds the biggest value, the last position holds a middle value, and the first position holds the smallest. Your job is to return true if even one such triple exists anywhere in the list, and false if none does. The smart way to solve this uses a stack, which we will explain in a moment, and a clever trick: we walk through the list backwards, from right to left.

mediumMonotonic StackStackTime: O(n) · Space: O(n)

Signals to notice

find subsequence i < j < k with nums[i] < nums[k] < nums[j]132 patterntrack candidates

Brute force first

Check all triplets. Triple nested loop. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Scan right to left with a monotonic decreasing stack. Track the largest 'popped' value as the candidate for nums[k] (the '2' in 132). If any element is smaller than this candidate, return true. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `nums=[3, 1, 4, 2]`

init: stack=[], third=-inf
i=3, nums[i]=2: 2<third(-inf)? no. while: stack empty. push 2 -> stack=[2]
i=2, nums[i]=4: 4<third(-inf)? no. while top 2<4: pop 2 -> third=2, stack=[]. push 4 -> stack=[4]
i=1, nums[i]=1: 1<third(2)? YES -> return True
Answer: True (subsequence [1,4,2]: 1 < 2 < 4)

What must stay true

The stack tracks candidates for the '3' (largest). Popped values become candidates for the '2' (second largest). If we find a '1' (smaller than the '2' candidate), the 132 pattern exists. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

stack = []; third = -inf
for i from n-1 down to 0:
    if nums[i] < third: return True        # found the '1'
    while stack and stack.top < nums[i]:    # nums[i] is a bigger '3'
        third = stack.pop()                 # largest valid '2' so far
    stack.push(nums[i])
return False

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Searching left-to-right — the right-to-left approach with stack is much cleaner because it naturally identifies the 3-2 pair and then checks for the 1. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Stack Pattern