132 Pattern

132 Pattern

What is this problem about?

The 132 Pattern interview question asks you to find if a subsequence of three integers $(nums[i], nums[j], nums[k])$ exists in an array such that $i < j < k$ and the values follow the relationship $nums[i] < nums[k] < nums[j]$. Essentially, you are looking for a "peak" where the value after the peak is smaller than the peak but larger than the value before it.

Why is this asked in interviews?

Companies like Goldman Sachs and Meta use this to test a candidate's ability to optimize a $O(N^3)$ or $O(N^2)$ brute-force approach down to $O(N)$. It requires sophisticated use of data structures to maintain state about past and future elements simultaneously.

Algorithmic pattern used

The optimal solution uses the Monotonic Stack interview pattern. By traversing the array from right to left, you can maintain a stack of potential "2" values (the $nums[k]$ candidates) while keeping track of the largest "2" found so far that has a larger "3" ($nums[j]$) to its left.

Example explanation

Array: [3, 1, 4, 2]

1. We want to find $i < j < k$ such that $nums[i] < nums[k] < nums[j]$.
2. Looking at [1, 4, 2]:

• $nums[i] = 1$
• $nums[j] = 4$
• $nums[k] = 2$

1. $1 < 2 < 4$ is true. The pattern exists.

Common mistakes candidates make

• Using Brute Force: Trying three nested loops will result in a Time Limit Exceeded error.
• Incorrect Stack Logic: Failing to maintain the "monotonic" property (elements in the stack should be strictly increasing or decreasing) which is key to finding the $nums[k]$ value.
• Confusing the order: Forgetting that the indices must be $i < j < k$; you cannot just pick any three numbers from the array.

Interview preparation tip

Monotonic stacks are the "secret weapon" for problems involving "next greater element" or relative ordering. If you need to find a value that is bounded by others on both sides, think of a stack.