Skip to main content

456. 132 Pattern

medium

Decide whether the array contains a subsequence i < j < k with nums[i] < nums[k] < nums[j]. The right-to-left monotonic-stack trick that surprises even seasoned interviewees.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j]. Return true if there is a 132 pattern in nums, otherwise, return false.

Constraints

  • n == nums.length
  • 1 <= n <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input
nums = [1,2,3,4]
Output
false

Explanation: There is no 132 pattern in the sequence.

Example 2

Input
nums = [3,1,4,2]
Output
true

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

Example 3

Input
nums = [-1,3,2,0]
Output
true

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Scan right to left. For each index j, we want a '2' (some value > nums[j]'s shadow) and an 'i' to the left with nums[i] < that '2'.

Hint 2

Maintain a monotonic decreasing stack of candidates for the '3' (the max value). When you see something bigger, pop and record the largest popped value as 'third' (the '2' candidate).

Hint 3

Now if any later (i.e., earlier in the array) nums[i] < third, you have a 132 pattern.

Hint 4

Track prefix-min as you go — but the cleaner version stores the '3' candidates and uses the largest popped value as 'third'.

Solution approach

Reveal approach

Right-to-left scan with a monotonic decreasing stack representing '3' candidates, and a variable 'third' representing the best '2' candidate found so far. Iterate i from n-1 down to 0: if nums[i] < third, return true (we have i with nums[i] < third, and an earlier-popped value > third sitting in the stack — that's the '3'). Otherwise, while the stack is non-empty and stack.top() < nums[i], pop and set third = max(third, popped) (these are valid '2' candidates because they're smaller than nums[i], our future '3'). Push nums[i]. If the loop completes without returning, return false. O(n) time and O(n) space — each element is pushed and popped at most once.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • monotonic-stack
  • array

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill 132 Pattern and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →