How to Solve 132 Pattern

To solve the 132 Pattern problem, traverse the array while maintaining a decreasing stack to track potential candidates for the '2' in the pattern. Compare each element with the minimums seen so far to detect a valid subsequence of form nums[i] < nums[k] < nums[j]. This approach efficiently handles large arrays while ensuring no valid pattern is missed.

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

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.

How GhostInterview Helps

• GhostInterview highlights pattern-specific stack operations to detect the 132 sequence efficiently.
• It guides users to track the left-side minimum and binary search for valid '2' candidates, reducing trial errors.
• The platform explains why certain brute-force approaches fail and shows optimal traversal strategies tied to the exact 132 pattern.

Topic Pages

• Array
• Binary Search
• Stack
• Monotonic Stack
• Ordered Set

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.