132 Pattern

How it works

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.

Steps

1. Initialize stkTop to n (stack starts empty) and k to negative infinity.
2. 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).
3. Return false if no pattern is found.

Complexity

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

Things to watch for

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.

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.

from typing import List

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

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        int stkTop = n;
        int k = INT_MIN;

        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) {
                return true;
            }

            while (stkTop < n && nums[i] > nums[stkTop]) {
                k = nums[stkTop++];
            }

            nums[--stkTop] = nums[i];
        }

        return false;
    }
};