132 Pattern — Scanning Right-to-Left with a Monotonic Stack

Problem Statement#

Given an array of n integers nums, return true if there is a 132 pattern: a subsequence of three integers nums[i], nums[j], nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Constraints:

• n == nums.length
• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

Input:  nums = [3,1,4,2]
Output: true
Explanation: nums[1]=1 < nums[3]=2 < nums[2]=4. Pattern at indices (1,2,3).

Input:  nums = [1,2,3,4]
Output: false

Why This Problem Matters#

132 Pattern is a medium problem where the name tells you the magnitude structure: find three numbers where the middle one is the largest (the "3"), the right one is middle-valued (the "2"), and the left one is smallest (the "1"). The indices must be in order: i < j < k.

The brute force is O(n³) or O(n²) — both fail for n up to 200,000. The O(n) monotonic stack solution is non-obvious and specifically tests whether you can think "from the right" instead of "from the left."

Amazon and Google use this problem to test right-to-left monotonic stack reasoning. Most candidates have seen left-to-right stack problems (Daily Temperatures, Next Greater Element). This problem forces right-to-left processing, which is the harder mental model. The key insight — maintain the "2" as a running variable using the stack — is a genuine interview filter.

The Core Insight#

The naming represents magnitude, not positions:

• The "1" (nums[i]) is the smallest, positioned leftmost.
• The "3" (nums[j]) is the largest, positioned in the middle.
• The "2" (nums[k]) is the middle value, positioned rightmost.

We need: nums[i] < nums[k] < nums[j] with i < j < k.

The right-to-left insight: Processing from right to left, at each position j, we want to know: has there been a valid "2" to the right of j (i.e., nums[k] for some k > j) that is less than nums[j]? If yes, then any element to the left of j that is smaller than this "2" completes the pattern.

Maintain a decreasing stack to track potential "3" values seen from the right, and a variable third to track the best "2" candidate (the largest value popped from the stack — it was smaller than some element that caused the pop, forming a valid "32" pair).

Visual Dry Run#

Input: nums = [3, 1, 4, 2]. Process right to left.

At i=2 (value=4): 4 > 2 in stack, so pop 2 and set third=2. Now 4 is the "3" and 2 is the "2" in a valid "32" pair.

At i=1 (value=1): 1 < third=2. This 1 is the "1", 4 is the "3", 2 is the "2". Pattern confirmed.

Solution (Optimal)#

class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        stack = []
        third = float('-inf')  # Best "2" candidate
 
        for num in reversed(nums):
            if num < third:
                return True  # Found the "1"
 
            while stack and stack[-1] < num:
                third = stack.pop()  # This element is a valid "2" for a "32" pair
 
            stack.append(num)
 
        return False

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

Time: O(n) — each element is pushed and popped from the stack at most once Space: O(n) — stack holds at most n elements

Common Mistakes#

• Processing left to right — a left-to-right approach requires tracking prefix minimums for the "1" candidate and is more complex; right-to-left is cleaner
• Checking num < third after the while loop — the check must happen BEFORE updating third; doing it after may miss a valid "1" because third has been overwritten
• Confusing third as the "3" (largest) instead of the "2" (middle value) — third tracks the element between "1" and "3" in value
• Initializing third to 0 — if all elements are negative, a 0 initialization causes false positives; always use -infinity

Interview Tips#

• Before coding, sketch the roles: "The '1' is the small leftmost element. The '3' is the large peak in the middle. The '2' is the rightmost element that falls between '1' and '3' in value."
• Explain why right-to-left: "Processing from the right lets me maintain the best '2' candidate seen so far. When I encounter a potential '3' (larger than the '2'), I record the old '2' by popping it. When I encounter a '1' (smaller than the '2'), the pattern is complete."
• If asked why the stack needs to be decreasing: "The stack maintains potential '3' values. When a larger '3' comes, it pops smaller potential '3's — those popped elements become '2' candidates."

Follow-up Questions#

• What is the brute force O(n²) approach? For each middle element (the "3"), track the prefix minimum to the left as the "1" candidate, then scan right for any element between the prefix minimum and the current element.
• How would you find all 132 patterns, not just detect one? Collecting all valid triplets could be O(n³) in the worst case. Counting them may be possible with a smarter approach but is problem-specific.
• What if the pattern is 123 (strictly increasing triplet)? LC 334 Increasing Triplet Subsequence — track the smallest element so far and the smallest valid second element; if you find a third element larger than both, return true.

Key Takeaways#

• Process right to left with a decreasing stack to solve 132 Pattern in O(n).
• The third variable tracks the "2" candidate — the largest element popped from the stack, which is part of a valid "32" pair to the right of the current position.
• Always check num < third BEFORE updating third in the while loop — order matters.
• Initialize third to negative infinity to handle arrays with all negative elements correctly.
• The "2" element is the one popped from the stack when a larger "3" arrives — it was smaller than the "3" and appeared to its right.
• Right-to-left processing is the harder mental model compared to standard left-to-right monotonic stack problems — this is what makes the problem a genuine interview filter.
• This problem demonstrates that not all monotonic stack problems scan left to right — knowing when to reverse direction is an advanced pattern-recognition skill.