456. 132 Pattern — DSA Atlas

456

MediumMonotonic Stack and Monotonic QueueMonotonic decreasing stack scanned right to left132 pattern detection

132 Pattern

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

Open official problem prompt ↗

In plain English

Decide whether some triple of positions forms the shape low, then highest, then a middle value strictly between them.

Picture it like this

Reading a stock chart backwards, you remember the highest peak you have passed and the best 'pullback' price just below a peak. If you ever reach an earlier price below that pullback, the up-then-partway-down pattern is confirmed.

Example

Input: nums = [3, 1, 4, 2]
Output: true
Why: Indices i=1, j=2, k=3 give nums[i]=1 < nums[k]=2 < nums[j]=4, matching the 1-3-2 shape.

Constraints

n == nums.length1 <= n <= 2 * 10^5-10^9 <= nums[i] <= 10^9

Pattern lesson

See the pattern, then code

132 pattern detection

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Scan from the right maintaining a decreasing stack of candidate '3' values. Whenever a value is popped because a larger value overtakes it, that popped value becomes the best available '2' (the k value). If any later-scanned element is smaller than this '2', we have found the '1' and a 132 pattern exists.

New words, made simpleKnow these before the algorithm

132 pattern: Three indices i<j<k with nums[i] < nums[k] < nums[j]: a low, then a high, then a middle.
The 'third' value: The largest value we have confirmed can act as the middle (the '2'), because some larger number sat to its left inside the stack.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force triples

Cubic, hopeless for n up to 2 * 10^5.

Check every i<j<k combination.

Time O(n^3)Space O(1)

Best choiceRight-to-left monotonic stack

Linear and the standard optimal solution.

Maintain decreasing candidate highs; promoted pops become the best middle to beat with a smaller left value.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack holds a strictly decreasing sequence of candidate '3' values, and third is the maximum value ever popped, i.e. the best middle for which a valid larger '3' exists to its right.

Why this is correct

Reasoning

A value is popped only when a larger value appears to its left (scanning right to left), so every popped value has a strictly greater number preceding it in index order, satisfying nums[j] > nums[k]. third keeps the largest such k. If any element scanned later (smaller index) is below third, it is the '1' with nums[i] < nums[k] < nums[j], a complete 132 pattern.

The algorithm in three movesSay these aloud before coding

1Track third = negative infinity, the best value that can serve as the '2' in 132

scan right: push 2 -> stack=[2]

2Iterate nums from right to left

x=4 pops 2 so third=2, push 4 -> stack=[4]

3If the current value is less than third, return true (it is the '1')

x=1 < third=2 -> return true

4While the stack top is smaller than the current value, pop it into third; then push the current value

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readx = 2

2 · AskBelow third (-inf)?

3 · Update statestack = []

4 · ResultNo; push 2, stack = [2].

Key takeaway

Scanning right, 4 promotes 2 to be the 'middle' (k); the later 1 undercuts it, completing 1-4-2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4State setup
third is the best middle value found so far; the stack holds decreasing potential highs to its right.
2
Lines 5-7Check for the '1'
If the current value is below third, it plays the low role and a full 132 pattern exists.
3
Lines 8-10Promote a middle
Popping smaller tops means the current x is a taller '3' to their left, so each popped value is a legitimate '2'; keep the largest in third.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Arrays of length < 3 always return false
A strictly increasing or strictly decreasing array has no 132 pattern
Duplicate values are handled because comparisons are strict

Common beginner mistakes

Scanning left to right, which makes it hard to guarantee the high sits between the low and middle
Using <= when popping and losing the strict inequality nums[k] < nums[j]
Returning true when only two of the three inequalities hold

Check your understanding

Why does scanning from the right make third a valid 'middle' value?

132 Pattern

132 Pattern

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue