132 Pattern

MediumMonotonic Stack🧩 Monotonic Stack LeetCode #456 ↗Updated Oct 30, 2026

Problem

You are given an integer array nums. Decide whether it hides three positions i < j < k whose values are shaped like the digits “1-3-2”: nums[i] < nums[k] < nums[j]. The three positions do not have to be adjacent. Return true if such a triple exists.

Inputnums = [1,2,3,4]Outputfalse

Inputnums = [3,1,4,2]Outputtrue (1, 4, 2)

Inputnums = [-1,3,2,0]Outputtrue (-1, 3, 2)

1 ≤ n ≤ 2·10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹

Try it yourself

Java

class Solution {
    public boolean find132pattern(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Scan from the right and treat each value as the “3”. Every smaller value it pops off a decreasing stack is a valid “2” for it; remember the largest popped value. If any later (further-left) number is below that, it is the “1”.

PatternMonotonic Stack

Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.

Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.

Open the Monotonic Stack guide →

Approaches

Brute ForceTry Every Triple

Time O(n³)Space O(1)

Enumerate all index triples i < j < k and test the inequality directly. It is the definition turned into code, so it is obviously correct and serves as a reference.

Java

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;
}

Correct but cubic — hopeless beyond a few hundred elements.

BetterFix the Middle, Use the Prefix Minimum

Time O(n²)Space O(1)

For a fixed middle j, the best possible “1” is the smallest value to its left — a smaller low end only widens the gap. Keep that prefix minimum as j advances, then look for any k > j that lands strictly inside (minLeft, nums[j]).

Java

public boolean find132pattern(int[] nums) {
    int n = nums.length;
    int minLeft = Integer.MAX_VALUE; // smallest value before j
    for (int j = 0; j < n; j++) {
        if (minLeft < nums[j]) {
            for (int k = j + 1; k < n; k++) {
                if (nums[k] > minLeft && nums[k] < nums[j]) return true;
            }
        }
        minLeft = Math.min(minLeft, nums[j]);
    }
    return false;
}

Drops one loop with a greedy choice, but still quadratic.

OptimalRight-to-Left Decreasing Stack

Time O(n)Space O(n)

Walk from the end keeping a stack of values that decreases toward the top. When nums[i] pops smaller values, each popped value sits to the right of a bigger one, so it is a legal “2”; keep the largest such value in third. Any later nums[i] < third completes the pattern. Each value is pushed and popped at most once.

Java

public boolean find132pattern(int[] nums) {
    int n = nums.length;
    int[] stack = new int[n];
    int top = -1;
    long third = Long.MIN_VALUE; // best "2" found so far
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] < third) return true; // nums[i] is the "1"
        // nums[i] acts as the "3": every smaller value on the stack can be its "2"
        while (top >= 0 && stack[top] < nums[i]) {
            third = stack[top--];
        }
        stack[++top] = nums[i];
    }
    return false;
}

Dry runnums = [1,2,3,4]

i current index changed

i=3
3

1

4

2
i
push 2, stack=[2]
i=2
3

1

4
i
2

pop 2 → third=2
i=2
3

1

4
i
2

push 4, stack=[4]
i=1
3

1
i
4

2

1 < third → true ✔

Linear time, one pass — the expected interview answer.

Pro tip

The stack is popped only when a bigger value appears, so third can only grow — it is always the largest “2” available.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Triple	`O(n³)`	`O(1)`
Better	Fix the Middle, Use the Prefix Minimum	`O(n²)`	`O(1)`
Optimal	Right-to-Left Decreasing Stack	`O(n)`	`O(n)`

Common pitfalls

Using non-strict comparisons — equal values never form a 132 pattern.
Scanning left-to-right with a stack and losing track of which value is the “1”.
Using Integer.MIN_VALUE as the sentinel when inputs may equal it — a long is safer.

Interview tips

Name the roles (“1”, “3”, “2”) before coding; it keeps the logic clear.
Bridge from O(n²): the prefix-minimum trick shows you think about greedy choices.
Explain why third never decreases — that is the correctness argument.

Pattern

Monotonic stack → when each element needs the nearest/best smaller or larger value on one side.

My notes saved in this browser