456. 132 Pattern - Explanation

1. Brute Force

Intuition

The most straightforward way to find a 132 pattern is to check every possible triplet. We need indices i < j < k where nums[i] < nums[k] < nums[j]. For each position k, we look backward to find a valid j (where nums[j] > nums[k]), and then look further back to find a valid i (where nums[i] < nums[k]). If all three conditions are met, we found the pattern.

Algorithm

Iterate k from index 2 to the end of the array.
For each k, iterate j backward from k - 1 to 1.
- Skip if nums[j] <= nums[k] since we need nums[j] > nums[k].
For each valid j, iterate i backward from j - 1 to 0.
- If nums[i] < nums[k], return true.
If no valid triplet is found, return false.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)

        for k in range(2, n):
            for j in range(k - 1, 0, -1):
                if nums[j] <= nums[k]:
                    continue

                for i in range(j - 1, -1, -1):
                    if nums[i] < nums[k]:
                        return True

        return False

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Stack

Intuition

Instead of checking every triplet, we can use a monotonic decreasing stack to efficiently track potential j candidates along with their corresponding minimum values to the left (potential i values). As we scan from left to right, we maintain a stack of pairs [nums[j], minLeft] where minLeft is the smallest element seen before index j. When we encounter a new element, if it's greater than the minLeft of any stack entry but less than that entry's value, we found a valid 132 pattern.

Algorithm

Initialize a stack to store pairs [num, minLeft] and track curMin as the running minimum.
For each element starting from index 1:
- Pop elements from the stack while the current element is greater than or equal to the top.
- If the stack is not empty and the current element is greater than stack.top().minLeft, return true.
- Push the current element with curMin onto the stack.
- Update curMin to be the minimum of itself and the current element.
Return false if no pattern is found.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []  # pair [num, minLeft], mono decreasing
        curMin = nums[0]

        for i in range(1, len(nums)):
            while stack and nums[i] >= stack[-1][0]:
                stack.pop()
            if stack and nums[i] > stack[-1][1]:
                return True

            stack.append([nums[i], curMin])
            curMin = min(curMin, nums[i])

        return False

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Stack (Optimal)

Intuition

We can solve this more elegantly by iterating from right to left. The key insight is to track k, which represents the largest valid "2" in a potential 132 pattern (the middle value that's smaller than some "3" to its right). We use a stack to maintain elements in decreasing order. When we find an element larger than the stack top, we pop elements and update k to be the largest popped value. If we ever find an element smaller than k, we've found our "1", completing the pattern.

Algorithm

Initialize an empty stack and set k to negative infinity.
Iterate from the end of the array to the beginning:
- If the current element is less than k, return true (we found the "1").
- While the stack is not empty and the top is less than the current element:
  - Pop and update k to the popped value (this becomes a candidate for "2").
- Push the current element onto the stack (candidate for "3").
Return false if no pattern is found.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack, k = [], float('-inf')

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < k:
                return True

            while stack and stack[-1] < nums[i]:
                k = stack.pop()
            stack.append(nums[i])

        return False

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Two Pointers

Intuition

We can achieve O(1) extra space by reusing the input array itself as a stack. The idea is the same as the optimal stack approach, but instead of using a separate stack, we use a pointer stkTop to track where our "stack" ends within the array. Elements from stkTop to n-1 form our virtual stack. This works because as we iterate from right to left, we no longer need the original values at those positions.

Algorithm

Initialize stkTop to n (stack starts empty) and k to negative infinity.
Iterate from the end of the array to the beginning:
- If the current element is less than k, return true.
- While stkTop < n and the current element is greater than nums[stkTop]:
  - Update k to nums[stkTop] and increment stkTop (pop from virtual stack).
- Decrement stkTop and store the current element at that position (push to virtual stack).
Return false if no pattern is found.

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        n = len(nums)
        stkTop, k = n, float('-inf')

        for i in range(n - 1, -1, -1):
            if nums[i] < k:
                return True

            while stkTop < n and nums[i] > nums[stkTop]:
                k = nums[stkTop]
                stkTop += 1

            stkTop -= 1
            nums[stkTop] = nums[i]

        return False

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Confusing the Pattern Order

The "132 pattern" refers to the relative ordering of values, not indices. You need nums[i] < nums[k] < nums[j] where i < j < k. A common mistake is looking for values in the wrong order or confusing which index maps to which part of the pattern name.

Using Wrong Comparison Operators

The pattern requires strict inequalities: nums[i] < nums[k] < nums[j]. Using <= instead of < will incorrectly accept patterns where two elements are equal.

# Wrong: allows equal values
if nums[i] <= nums[k] <= nums[j]:
# Correct: requires strict inequalities
if nums[i] < nums[k] < nums[j]:

Forgetting to Track the Minimum Correctly

In the stack-based approach, you must track the minimum value to the left of each potential "3" (middle element). Failing to update the minimum correctly or associating it with the wrong stack element leads to missing valid patterns or false positives.