132 Pattern

Problem Statement

Given an array of integers nums, find if there exists a subsequence of three integers nums[i], nums[j], nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. In other words, find three elements in order where the first is the smallest, the third is in the middle, and the second is the largest — a "132" pattern.

Example 1:

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

Example 2:

Input: nums = [3, 1, 4, 2]
Output: true
Explanation: nums[1]=1, nums[2]=4, nums[3]=2 → 1 < 2 < 4 → 132 pattern.

Example 3:

Input: nums = [-1, 3, 2, 0]
Output: true
Explanation: nums[0]=-1, nums[1]=3, nums[2]=2 → -1 < 2 < 3 → 132 pattern.

Constraints:

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

Difficulty: Medium (LC 456)

---

Pattern Recognition

• What is the input structure? An array of integers where we search for a specific subsequence pattern.
• What are we optimizing? Finding three elements in a particular relative order.
• What pattern does this fit? Monotonic Stack, processed from right to left. The stack maintains candidates for the "3" role (the largest element), while tracking the maximum "2" candidate (the middle element) seen so far.
• Why does this pattern fit? Scanning from right to left, the stack holds potential "3" values in decreasing order. When a new value pops elements off the stack, those popped elements become candidates for "2" (since they are smaller than "3" but we want the largest such value). Then any element to the left that is smaller than "2" completes the pattern.

---

Approach

Brute Force — Triple Nested Loops

Check all triplets (i, j, k) with i < j < k.

for i in 0..n-3:
    for j in i+1..n-2:
        for k in j+1..n-1:
            if nums[i] < nums[k] < nums[j]:
                return true
return false

Time: O(n^3). Space: O(1). Why insufficient: For n = 2 * 10^5, this is 10^15 operations.

Better — Two Loops with Prefix Min

Maintain min_so_far (prefix minimum up to j) as the "1" candidate. For each j, scan right for a "2" that satisfies min_so_far < nums[k] < nums[j].

Time: O(n^2). Space: O(1). Why insufficient: Still quadratic — too slow.

Optimal — Monotonic Stack (Right to Left)

Key Insight: Process from right to left. Maintain a stack of decreasing values (candidates for "3" — the largest value). When you encounter a value larger than the stack top, pop elements — they become candidates for "2" (the middle value). Track the maximum popped value as second. Then, any element to the left that is less than second completes the "1 < 2 < 3" pattern.

Step-by-step:

1. Initialize stack = [] and second = -infinity (the "2" in the 132 pattern — the middle value, which must be the largest "2" candidate found so far).
2. Traverse nums from right to left:
   • If nums[i] < second, we found a "1" — return true. (We already have a "3" > "2" to the right.)
   • While stack is not empty and stack[-1] < nums[i]:
     • Pop the top. This popped value is a "2" candidate (it is < current element, which becomes "3").
     • Update second = max(second, popped).
   • Push nums[i] onto the stack (it is a "3" candidate).
3. If no pattern found, return false.

function find132pattern(nums):
    stack = []
    second = -infinity  # Best "2" candidate (middle value)
    for i from n-1 down to 0:
        if nums[i] < second:
            return true  # nums[i] is the "1"
        while stack and stack.top < nums[i]:
            second = max(second, stack.pop())  # Popped becomes "2"
        stack.push(nums[i])  # Current is "3" candidate
    return false

Time: O(n) — each element is pushed and popped at most once. Space: O(n) for the stack.

---

Walkthrough

nums = [3, 1, 4, 2]

Processing right to left:

Step	i	nums[i]	Check nums[i] < second?	Stack before	Pop?	second	Stack after push
1	3	2	2 < -inf? No	[]	—	-inf	[2]
2	2	4	4 < -inf? No	[2]	2 < 4, pop 2 → second = 2	2	[4]
3	1	1	1 < 2? Yes!	—	—	—	—

Return true! The pattern is: 1 (nums[1]) < 2 (second) < 4 (nums[2]), which maps to indices 1, 2, 3.

---

Harder example: nums = [1, 0, 1, -4, -3]

Processing right to left:

Step	i	nums[i]	Check < second?	Stack before	Pop?	second	Stack after
1	4	-3	-3 < -inf? No	[]	—	-inf	[-3]
2	3	-4	-4 < -inf? No	[-3]	-4 < -3? No push	-inf	[-3, -4]
3	2	1	1 < -inf? No	[-3, -4]	pop -4 (< 1) → s=-4; pop -3 (< 1) → s=-3	-3	[1]
4	1	0	0 < -3? No	[1]	0 < 1? No push	-3	[1, 0]
5	0	1	1 < -3? No	[1, 0]	pop 0 (< 1) → s=max(-3,0)=0	0	[1, 1]

No element was < second when checked. But wait — at step 5, after updating second to 0, we push 1. The check happens before popping. Let me re-examine: the check nums[i] < second at step 5 is 1 < -3 which is false. After popping and updating second to 0, there is no re-check. So no 132 pattern found.

Return false. — Correct! There is no valid 132 pattern in [1, 0, 1, -4, -3].

---

Implementation

TypeScript

function find132pattern(nums: number[]): boolean {
    const stack: number[] = []; // Candidates for "3" (decreasing order)
    let second = -Infinity;     // Best "2" candidate found so far

    // Process right to left
    for (let i = nums.length - 1; i >= 0; i--) {
        // If current element is less than second, we found "1"
        if (nums[i] < second) return true;

        // Pop elements smaller than current — they become "2" candidates
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            second = Math.max(second, stack.pop()!);
        }

        // Current element is a "3" candidate
        stack.push(nums[i]);
    }

    return false;
}

C++

bool find132pattern(vector<int>& nums) {
    stack<int> stk;             // Candidates for "3" (decreasing order)
    int second = INT_MIN;       // Best "2" candidate found so far

    // Process right to left
    for (int i = (int)nums.size() - 1; i >= 0; i--) {
        // If current element is less than second, we found "1"
        if (nums[i] < second) return true;

        // Pop elements smaller than current — they become "2" candidates
        while (!stk.empty() && stk.top() < nums[i]) {
            second = max(second, stk.top());
            stk.pop();
        }

        // Current element is a "3" candidate
        stk.push(nums[i]);
    }

    return false;
}

Watch out:

1. Confusing which role is which. In the "132" pattern: "1" is the smallest (leftmost), "3" is the largest (middle position), "2" is the middle value (rightmost position). The naming follows the pattern shape, not the value ordering. This is confusing — draw it out.
2. Checking nums[i] < second after popping. The check must happen BEFORE popping. If you pop first and then check, you might use a stale second value. The current element could be the "3", so you should not check it as a "1" after updating second.
3. Initializing second to 0 instead of -inf. The values can be negative. Using 0 would miss patterns where all values are negative.

---

Complexity Analysis

	Time	Space
Brute Force (Triple Loop)	O(n^3)	O(1)
Prefix Min + Scan	O(n^2)	O(1)
Monotonic Stack	O(n)	O(n)

Bottleneck: Each element is pushed onto the stack at most once and popped at most once, giving O(n) total stack operations. The space is O(n) in the worst case (strictly decreasing array — nothing gets popped).

---

Edge Cases

1. Strictly increasing array [1, 2, 3, 4] — No 132 pattern. The "3" is always the last element, but there is no element after it to serve as "2".
2. Strictly decreasing array [4, 3, 2, 1] — No 132 pattern. No element is larger than a later element.
3. Array with 3 elements — The simplest possible case. Check directly.
4. Pattern at the very end [5, 1, 6, 3] — 1 < 3 < 6. The algorithm finds this on the last scan step.
5. Negative numbers [-2, 1, -1] — -2 < -1 < 1. Must handle negatives correctly.
6. Duplicate values [1, 2, 2] — Not a valid 132 pattern (need strict inequalities). nums[i] < nums[k] < nums[j].

---

Related Problems

• LC 334 — Increasing Triplet Subsequence — Find i < j < k with nums[i] < nums[j] < nums[k]. Simpler pattern (strictly increasing), solvable with two variables in O(n).
• LC 503 — Next Greater Element II — Monotonic stack for finding the next greater element. Same stack technique.
• LC 739 — Daily Temperatures — Monotonic stack to find the next warmer day.
• LC 42 — Trapping Rain Water — Uses a monotonic stack to find boundaries. Same family of stack-based problems.

---

What is Expected at Each Level

Junior: Understand the problem statement (the naming is confusing). Write the O(n^2) approach with prefix minimum. May not see the stack solution.

Mid-level: Arrive at the monotonic stack approach. Correctly identify the roles: stack holds "3" candidates, popped values become "2" candidates. Write bug-free code. Explain why processing right-to-left works.

Senior: Write the solution quickly. Prove correctness: why is tracking the maximum popped value sufficient? Why does the order of check-then-pop matter? Extend to: "Find the 132 pattern with maximum nums[j] - nums[i]." Discuss alternative approaches (TreeSet/SortedList for online "2" candidate tracking). Connect to the general framework of monotonic stack problems.