MediumMonotonic Stack

132 Pattern

Explanation & Solution

Description

Given an array of n integers nums, return true if there exists a 132 pattern in the array.

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].

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

Output: false

Explanation: There is no 132 pattern in the sequence.

Monotonic Stack pattern

If the array has fewer than 3 elements, return false immediately since a 132 pattern requires at least three values.

Create an empty stack that will maintain a decreasing order from bottom to top.
Initialize third to -Infinity. This variable tracks the best candidate for the "2" in the 132 pattern (i.e., nums[k], the middle value that is less than nums[j] but greater than nums[i]).

Traverse the array from the last element to the first.
For each element nums[i], check if it is less than third. If so, we have found a valid "1" — an element smaller than both the "3" (which was on the stack) and the "2" (third). Return true.

While the stack is not empty and the top of the stack is less than nums[i], pop elements from the stack.
Each popped element becomes the new third, because it was smaller than the current nums[i] (which acts as the "3" in the pattern), making it a valid "2" candidate.
Push nums[i] onto the stack.

If the entire array is traversed without finding a valid "1" element, return false.

By iterating from right to left, we use a monotonic stack to efficiently track the largest possible "2" value (third) that is smaller than some "3" value already seen. The moment we encounter a "1" value smaller than third, the 132 pattern is confirmed.

Time

O(n)each element is pushed and popped from the stack at most once.

Space

O(n)the stack can hold up to n elements in the worst case.

Input:

[1, 2, 3, 4]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps