#456

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

132 Pattern

Identify whether a given integer array contains a 132 pattern subsequence using efficient stack and search techniques.

array binary search stack monotonic stack ordered set

Problem Statement

Given an integer array nums, determine whether there exists a subsequence of three integers nums[i], nums[j], nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. A subsequence does not need to occupy consecutive positions, but must maintain relative order.

Return true if such a 132 pattern exists within the array; otherwise, return false. For example, nums = [3,1,4,2] contains the subsequence [1,4,2], which satisfies the 132 pattern, while nums = [1,2,3,4] does not contain any valid 132 pattern.

Examples

Example 1

Input: nums = [1,2,3,4]

Output: false

There is no 132 pattern in the sequence.

Example 2

Input: nums = [3,1,4,2]

Output: true

There is a 132 pattern in the sequence: [1, 4, 2].

Example 3

Input: nums = [-1,3,2,0]

Output: true

There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints

n == nums.length
1 <= n <= 2 * 105
-109 <= nums[i] <= 109

Solution Approach

Use a monotonic stack to track potential '3' values

Iterate from the end of the array toward the start, maintaining a stack of candidates for nums[j] in descending order. Pop elements smaller than the current value to update the maximum '2' candidate. If the current element is smaller than the tracked '2', return true immediately.

Track the minimum element for the '1' position

Precompute or update the minimum element to the left of each index to quickly validate the '1' in the 132 pattern. During iteration, ensure that the current '3' candidate is greater than this minimum before checking for a valid '2' in the stack.

Binary search over valid '2' candidates for optimization

If using a sorted data structure or ordered set to maintain potential '2' candidates, perform a binary search to find a candidate between the tracked minimum '1' and current '3' value. This reduces unnecessary stack or array traversal in dense sequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) using a single pass with a monotonic stack or O(n log n) when binary searching over a sorted set of '2' candidates. Space complexity is O(n) for storing the stack or ordered set for candidate tracking.

What Interviewers Usually Probe

Candidate considers tracking min values for '1' positions and stack management for '3'.
Candidate attempts O(n^2) brute force and may need guidance toward monotonic stack or binary search over valid answers.
Candidate mentions handling negative numbers and duplicate elements carefully to avoid false negatives.

Common Pitfalls or Variants

Common pitfalls

Assuming the 132 pattern elements must be consecutive rather than a subsequence.
Failing to update or correctly maintain the stack or min value, causing missed patterns.
Overcomplicating with unnecessary nested loops instead of using a single-pass stack approach.

Follow-up variants

Detect 321 or 213 patterns instead, adjusting stack logic accordingly.
Return all indices of valid 132 patterns instead of just true/false.
Handle streaming input where the array is too large to store entirely in memory.

FAQ

What is the 132 pattern in an array?

A 132 pattern is a subsequence of three integers nums[i], nums[j], nums[k] where i < j < k and nums[i] < nums[k] < nums[j].

Can duplicates exist in the 132 pattern detection?

Yes, duplicates can exist elsewhere in the array, but the relative order of the subsequence must satisfy nums[i] < nums[k] < nums[j].

What is an efficient way to detect a 132 pattern?

Use a monotonic stack while traversing the array from the end and track the minimum element for '1' to detect the pattern in O(n) time.

Why is a monotonic stack used in this problem?

It efficiently tracks potential '3' values while allowing fast comparison against the '2' candidate without checking all previous elements.

Can binary search optimize finding the '2' in the 132 pattern?

Yes, using an ordered set or sorted structure allows binary search to find a valid '2' candidate between the minimum '1' and current '3', reducing unnecessary checks.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vk = -inf
        stk = []
        for x in nums[::-1]:
            if x < vk:
                return True
            while stk and stk[-1] < x:
                vk = stk.pop()
            stk.append(x)
        return False

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        vk = -inf
        stk = []
        for x in nums[::-1]:
            if x < vk:
                return True
            while stk and stk[-1] < x:
                vk = stk.pop()
            stk.append(x)
        return False

Continue Practicing

#975 odd even jump #493 reverse pairs #496 next greater element i