We need to find three elements in the array, in order from left to right, that form a specific pattern: the first element is the smallest, the third is in the middle, and the second is the largest. In other words, we need indices i < j < k where nums[i] < nums[k] < nums[j].

The naming "132 pattern" comes from the relative ordering of the values: position 1 has the smallest value, position 3 has the middle value, and position 2 has the largest value. So despite the indices being in order (i, j, k), the values follow a "small, big, medium" pattern.

What makes this problem tricky is that we can't just look at consecutive elements. The three elements can be anywhere in the array, as long as their indices are in increasing order. So we need a way to efficiently track candidates for each role in the pattern.

The key observation is this: if we can find a pair (nums[j], nums[k]) where j < k and nums[k] < nums[j], then we just need to check if there's any element before index j that's smaller than nums[k]. That reframes the problem into something more manageable.

Key Constraints:

Intuition

The most straightforward way to solve this is to check every possible triplet (i, j, k). For each combination of three indices where i < j < k, we check if nums[i] < nums[k] < nums[j]. If we find any such triplet, we return true.

This directly translates the problem statement into code without any clever observations.

Algorithm

Code

This brute force checks every triplet, which is far too slow for large inputs. What if we precomputed the minimum value to the left of each index so the "i" role is handled in O(1)?

Intuition

For the "1" in the 132 pattern (the smallest element), we always want the smallest possible value to the left of index j. The smaller nums[i] is, the wider the window for nums[k] to fit between nums[i] and nums[j]. So instead of trying every possible i, we can precompute a prefix minimum array.

With the prefix minimum in hand, we iterate over each j from left to right. For each j, we know the minimum value to its left (our candidate for nums[i]). Now we just need to find any k > j where prefixMin[j] < nums[k] < nums[j]. We can do this with a simple inner loop scanning from j+1 to the end.

This reduces the problem from three nested loops to two.

Algorithm

Example Walkthrough

Code

The prefix minimum eliminates one loop, but we're still scanning right for each j. What if we processed the array from right to left and used a stack to efficiently track the best candidate for nums[k]?

Intuition

The idea is to iterate from right to left, using a stack to track candidates for the "3" (nums[j], the largest value) and simultaneously tracking the best candidate for the "2" (nums[k], the middle value).

As we scan from right to left, we maintain a stack of elements. When we encounter an element that's larger than the top of the stack, we pop elements from the stack. Each popped element is smaller than the current element, which means the current element could be nums[j] and the popped element could be nums[k] in a 132 pattern. Among all popped elements, the largest one gives us the best chance of finding a nums[i] that's smaller than it.

So we keep track of the maximum value we've popped from the stack, called third. If at any point the current element is less than third, we've found our 132 pattern: the current element is nums[i], some element to its right that caused the pop is nums[j], and third is nums[k].

Algorithm

Example Walkthrough

Code