132 Pattern: Monotonic Stack from the Right

LeetCode 132 Pattern (problem 456) asks whether an array of integers contains a "132 pattern." That means three elements nums[i], nums[j], nums[k] where i < j < k and nums[i] < nums[k] < nums[j]. The naming comes from the relative sizes: the first element is smallest (the "1"), the second is largest (the "3"), and the third is in between (the "2").

The problem

Given an array of n integers nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[k] < nums[j]. Otherwise, return false.

Example: nums = [3, 1, 4, 2]. The answer is true because the subsequence (1, 4, 2) at indices (1, 2, 3) satisfies 1 < 2 < 4.

Why this problem matters

The 132 pattern is one of the cleanest demonstrations of how a monotonic stack can solve problems that seem to require nested loops. A brute-force triple loop runs in O(n^3), and even smarter pairwise approaches sit at O(n^2). The monotonic stack solution brings this down to O(n), which is a dramatic improvement for large inputs.

This problem also trains you to think about scanning direction. Most monotonic stack problems scan left to right. Here, scanning right to left is the key insight. That reversal lets you maintain a stack of "potential j values" (the largest element in the pattern) while tracking the best "k value" (the middle element) separately. Learning to flip the scan direction when the standard approach does not fit is a skill that transfers to many other problems.

Finally, the 132 pattern reinforces how to decompose a multi-element condition into manageable invariants. You are not searching for three elements simultaneously. Instead, you fix a role for each data structure: the stack holds candidates for the largest value, a variable holds the best middle value, and any element smaller than that variable completes the pattern.

The key insight

Scan the array from right to left. Maintain a monotonically decreasing stack. The stack holds elements that are candidates for the "j" role (the largest value in the 132 triple). Keep a variable called third that tracks the best candidate for the "k" role (the middle value).

At each index, before pushing the current element onto the stack, pop all elements from the stack that are smaller than the current element. Each popped value becomes a new candidate for third, and you update third to the maximum of all popped values. Then push the current element onto the stack.

After updating the stack and third, check whether the current element is less than third. If it is, you have found the "i" role (the smallest value), which means a valid 132 pattern exists.

Why does this work? The stack is decreasing, so everything on the stack is larger than third. When you find a current value that is less than third, you know there is some value on the stack (or that was on the stack) that is larger than third, and third itself is larger than the current value. That gives you nums[i] < nums[k] < nums[j].

The code

def find132pattern(self, nums):
    stack = []
    third = float('-inf')

    for i in range(len(nums) - 1, -1, -1):
        if nums[i] < third:
            return True
        while stack and stack[-1] < nums[i]:
            third = stack.pop()
        stack.append(nums[i])

    return False

Why this works

The loop iterates from the last index to the first. At every step, the stack contains a decreasing sequence of values that appeared to the right of the current index. The variable third stores the largest value that was ever popped from the stack.

When you encounter nums[i] and it is greater than some elements on the stack, those smaller elements get popped. The last (largest) popped value becomes third. This is safe because the popped value was smaller than the element that caused the pop, and it appeared to the right of that element in the original array. So there exists a pair (nums[j], nums[k]) where nums[k] = third and nums[j] is at least as large as the current element (since it is still on the stack or is the current element itself).

Now, if any future element (further to the left) is less than third, you have all three roles filled: nums[i] < third < nums[j].

Visual walkthrough

The walkthrough above traces through nums = [3, 1, 4, 2]. At index 2, the element 4 is larger than the stack top (2), so 2 gets popped and third becomes 2. At index 1, the element 1 is less than third (2), so the function returns true. The full 132 pattern is (1, 4, 2).

Complexity analysis

Time: O(n). Each element is pushed onto the stack at most once and popped at most once. The total number of push and pop operations across all iterations is at most 2n, so the amortized cost per element is O(1).

Space: O(n). In the worst case (a strictly decreasing array), every element stays on the stack.

Building blocks

Monotonic decreasing stack

A monotonic decreasing stack keeps elements in non-increasing order from bottom to top. When a new element is larger than the top, you pop until the invariant is restored. This pattern appears in problems like Daily Temperatures and Largest Rectangle in Histogram. The key property is that popped elements are "dominated" by the incoming element.

Right-to-left scanning

Most stack problems process elements left to right. Scanning right to left flips the perspective: the stack represents elements to the right of the current position. This is useful when you need to reason about elements that come after the current one in the array, which is exactly what the 132 pattern requires for the "j" and "k" roles.

Edge cases

• Array with fewer than 3 elements. No 132 pattern can exist. The loop simply runs without finding nums[i] < third, and the function returns false.
• Strictly increasing array. For example, [1, 2, 3, 4]. No element to the right is both larger and has a smaller element between them. The stack stays decreasing, third remains negative infinity, and the answer is false.
• Strictly decreasing array. For example, [4, 3, 2, 1]. Nothing gets popped because each new element is smaller than the stack top. third stays at negative infinity, and the answer is false.
• Duplicate values. The strict inequalities nums[i] < nums[k] < nums[j] mean equal values do not form a valid pattern. For [1, 1, 1], the answer is false.

From understanding to recall

The recognition trigger for the 132 pattern is any problem that asks you to find three elements in a specific relative order where the middle index holds the largest value. The monotonic stack approach is the go-to tool because it lets you track "what is the largest value to my right that has something even larger further right?" in O(n) time.

When you practice this problem, focus on internalizing two things. First, the right-to-left scan direction is what makes the stack represent future elements. Second, the third variable is the bridge between the stack and the current element. Once those two pieces click, you can reconstruct the solution from scratch without memorizing the code.

Related posts

• Daily Temperatures - Another monotonic stack problem
• Largest Rectangle in Histogram - Stack-based array processing
• Next Permutation - Pattern recognition in arrays