132 Pattern — Monotonic Stack Right-to-Left in O(n)

Problem Statement#

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

Constraints:

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

Input:  nums = [1,2,3,4]
Output: false
Explanation: No 132 pattern exists in a strictly increasing array.

Input:  nums = [3,1,4,2]
Output: true
Explanation: i=1 (1), j=2 (4), k=3 (2). 1 < 2 < 4. ✓

Input:  nums = [-1,3,2,0]
Output: true
Explanation: -1 < 0 < 3 (or 2).

Why This Problem Matters#

LeetCode 456 132 Pattern is a Bloomberg favorite that also shows up regularly at Amazon and Google. It is one of the few problems where a monotonic stack scanned right-to-left is the optimal solution. Most candidates struggle because the natural reading order is left-to-right, so the trick of reversing direction is genuinely tricky.

This problem teaches:

• How to identify a "next" relationship — here, the next number to the right that is smaller than the current peak.
• Why scanning direction matters when applying a monotonic stack.
• A subtle pattern: keep track of the best candidate for nums[k] (the "2" in 132) while ensuring it remains less than nums[j] (the "3").

It is the canonical bridge between "next greater element" problems and harder problems like LC 1856 and LC 2104.

The Core Insight#

A 132 pattern needs:

• nums[i] = some small value (the "1").
• nums[j] = a peak value (the "3").
• nums[k] = a middle value strictly between nums[i] and nums[j], and k > j.

We scan from right to left and maintain:

• A monotonically decreasing stack from bottom to top (top has the smallest value seen so far) of candidate nums[j] values.
• A variable third representing the best (largest) value we have already discarded from the stack — this is our candidate nums[k] (the "2").

When we examine nums[i]:

• If nums[i] < third, we have found a pattern: nums[i] = "1", the popped element that became third = "3" (wait — actually: the element that promoted third was a j > i and third is a number to its right, smaller than it). Return true.
• Otherwise, while the stack top is less than nums[i], pop and update third = max(third, popped). This means: nums[i] is bigger than something on the stack, so we promote that smaller value to be a nums[k] candidate, with nums[i] itself becoming the new nums[j].
• Push nums[i].

The clever part: third is always strictly less than at least one value to its left in the stack (the value that pushed it out). So if we ever find an nums[i] < third, the triplet (nums[i], that_value, third) forms a valid 132 pattern.

O(n) time because each element is pushed and popped at most once.

Visual Dry Run#

Input: nums = [3, 1, 4, 2]. Scan right to left: indices 3, 2, 1, 0.

Found pattern at indices (1, 2, 3) with values (1, 4, 2): 1 < 2 < 4. ✓

Input: nums = [1, 2, 3, 4].

Loop ends. Return false. No 132 pattern in a strictly increasing array.

Solution (Optimal)#

# Python — monotonic stack right-to-left, O(n) time, O(n) space
def find132pattern(nums: list[int]) -> bool:
    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 = max(third, stack.pop())
        stack.append(nums[i])
 
    return False

// JavaScript — monotonic stack right-to-left, O(n) time, O(n) space
function find132pattern(nums) {
    const stack = [];
    let third = -Infinity;
 
    for (let i = nums.length - 1; i >= 0; i--) {
        if (nums[i] < third) return true;
        while (stack.length && stack[stack.length - 1] < nums[i]) {
            third = Math.max(third, stack.pop());
        }
        stack.push(nums[i]);
    }
 
    return false;
}

# Brute force for reference, O(n^2) time
def find132patternBrute(nums: list[int]) -> bool:
    n = len(nums)
    for j in range(n):
        min_left = min(nums[:j], default=float('inf'))
        for k in range(j + 1, n):
            if min_left < nums[k] < nums[j]:
                return True
    return False

Complexity:

Common Mistakes#

1. Scanning left-to-right. The pattern nums[i] < nums[k] < nums[j] with i < j < k is hard to detect left-to-right because you do not know which value will be the future "2." Scanning right-to-left lets us treat each element as a potential nums[i] while keeping nums[k] and nums[j] candidates already known.

2. Not updating third correctly. third must be the maximum popped value, not the most recent. Some popped value might be a better (larger) candidate for nums[k].

3. Pushing before checking. If you push nums[i] first and then check nums[i] < third, you can falsely match nums[i] against itself.

4. Treating "<" as "<=" in the comparison. The pattern requires strict inequalities. Using <= gives false positives for arrays like [1, 2, 2].

5. Stack monotonicity confusion. The stack stays monotonically decreasing from bottom to top while scanning right-to-left because we only pop when a strictly larger element arrives.

Interview Tips#

• Open with: "I will scan right-to-left because the relationship nums[i] < nums[k] < nums[j] with i < j < k is more naturally tracked by maintaining future j and k candidates as we move backward through i."
• Justify the monotonic stack: "A decreasing stack lets me know that when an element pops, the popper is a larger value to its left — perfect candidate for nums[j]."
• Walk through the example [3, 1, 4, 2] to convince the interviewer the logic is sound. The right-to-left scan is unintuitive enough that most interviewers want to see a trace.
• If the interviewer asks "what about [1, 4, 2, 3]?" walk through it: scan finds third = 2 after popping, then sees 1 < 2, returns true.

Follow-up Questions#

1. Return all 132 patterns. Tracking just third is no longer enough; you must reconstruct triples — typically O(n^2) for output sensitivity.
2. Find the longest 1...3...2 subsequence. Generalizes to LIS-style DP and is much harder.
3. Streaming variant. Incrementally maintain the answer as nums grows — non-trivial extension.
4. 123 pattern. Strictly increasing — trivial in O(n) with two pointers.
5. Generalized k-pattern detection. Brute force is O(n^k); segment trees or BIT can reduce some cases.

Key Takeaways#

• 132 Pattern is the canonical "scan right-to-left with a monotonic stack" problem on the LeetCode catalog.
• Maintain a decreasing stack of candidate nums[j] values; when you pop, the popped value becomes a candidate for nums[k] ("2"), tracked in third.
• A 132 pattern is found when the current element is strictly less than third — that means a smaller nums[i], a popped nums[k], and the popper nums[j] form a valid triple.
• O(n) time and O(n) space because each element is pushed and popped at most once.
• The right-to-left direction is the key insight — many monotonic stack problems benefit from reversing the scan direction.
• Watch out for <= vs < and for resetting third only via max(third, popped).