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 Sam K., 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

More Stacks practice problems

See all Stacks problems →