132 Pattern — Monotonic Stack from Right

Problem

Find if there exist indices i < j < k such that nums[i] < nums[k] < nums[j].

Approach — Monotonic Stack Right to Left

Scan right to left. Maintain decreasing stack. When popping (found smaller), that's our nums[k] candidate (the '2' in 132). If current num < candidate, we found 132 pattern.

Time: O(n) | Space: O(n)

Solutions

Python

class Solution:
    def find132pattern(self, nums: list[int]) -> bool:
        stack=[]; third=float('-inf')  # 'k' value (the '2' in 132)
        for n in reversed(nums):
            if n<third: return True
            while stack and stack[-1]<n:
                third=stack.pop()
            stack.append(n)
        return False

Complexity

• Time: O(n) | Space: O(n)