Skip to main content
Talentd

132 Pattern - Solution & Explanation

MediumArrayBinary SearchStackMonotonic Stack11 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

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.

 

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].

 

Constraints:

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

Approach Overview

Problem Overview: The task is to determine whether an integer array contains a 132 pattern: three indices i < j < k such that nums[i] < nums[k] < nums[j]. You need to check if there exists a subsequence where the first value is the smallest, the second is the largest, and the third falls strictly between them.

Approach 1: Brute Force (O(n³) time, O(1) space)

The straightforward approach checks every possible triple (i, j, k). Use three nested loops: iterate i from the start, j after i, and k after j. For each combination, verify whether nums[i] < nums[k] < nums[j]. The logic is simple and mirrors the exact definition of the pattern. However, the algorithm performs roughly n³ comparisons, which becomes impractical for large arrays. This method mainly serves as a baseline to confirm understanding of the pattern definition before moving to an optimized approach using a array traversal strategy.

Approach 2: Stack Optimization (O(n) time, O(n) space)

The optimal solution uses a decreasing stack while scanning the array from right to left. The key idea is to track potential candidates for the nums[j] and nums[k] values while searching for a smaller nums[i]. Maintain a variable (often called third) that stores the best candidate for nums[k]. While iterating backward, if the current element is smaller than third, a valid 132 pattern exists.

Otherwise, pop elements from the stack while the current value is greater than the stack top. Each popped value becomes a stronger candidate for nums[k] because it lies between a future larger element and a smaller prefix element. After popping, push the current value onto the stack to maintain a decreasing order. This structure behaves like a monotonic stack, ensuring every element is pushed and popped at most once, giving linear time complexity.

This method works because scanning from the right naturally preserves valid ordering for j and k. The stack keeps possible nums[j] values, while the third variable tracks the largest valid nums[k] discovered so far. The moment you encounter a smaller number to the left, the pattern is confirmed.

Recommended for interviews: Interviewers typically expect the stack-based O(n) approach. The brute force method shows that you understand the pattern definition and constraints, but the optimized solution demonstrates familiarity with monotonic stack techniques and efficient array scanning strategies often used in advanced array problems.

Approach 1: Approach 1: Brute Force

This approach checks all possible triples (i, j, k) to determine if they form a 132 pattern. While straightforward, its complexity can be high for larger arrays due to the triple nested loop structure.

The code iterates over all possible triplets to check if the condition nums[i] < nums[k] < nums[j] holds. If such a triplet is found, it returns true. Otherwise, after all checks, it returns false.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n^3) because of the three nested loops.
Space complexity: O(1) since no additional data structures are used.

Try this approach in the editor →

Approach 2: Approach 2: Stack Optimization

This approach uses a clever stack-based strategy by scanning the array from right to left. It keeps track of potential '2' and '3' candidates using a stack and a variable, optimizing the search for the '132' pattern.

Iterate from the end of the array to the beginning. The stack is used to keep track of elements greater than a possible '2' in the pattern. 'num3' holds the maximum candidate for '2'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n) because each element is pushed and popped once.
Space complexity: O(n) for the stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Brute Force

Time complexity: O(n^3) because of the three nested loops.
Space complexity: O(1) since no additional data structures are used.

Approach 2: Stack Optimization

Time complexity: O(n) because each element is pushed and popped once.
Space complexity: O(n) for the stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(n³)O(1)Useful for understanding the definition of the 132 pattern or verifying small inputs.
Monotonic Stack OptimizationO(n)O(n)Best choice for interviews and large arrays; scans once using a decreasing stack.

Video Solution

132 Pattern - Leetcode 456 - Python • NeetCode • 80,620 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is 132 Pattern easy or hard?
132 Pattern is generally rated Medium difficulty. The brute force idea is straightforward, but discovering the optimal O(n) monotonic stack solution requires deeper understanding of stack patterns and reverse traversal techniques.
132 Pattern Python/Java solution
Most implementations use a stack and a variable storing the potential 'ak' value. The algorithm iterates from right to left, pops smaller stack elements to update the middle value, and checks if the current number forms a valid ai < ak relationship. The same logic works across Python, Java, C++, and other languages.
How to solve 132 Pattern in O(n)?
Traverse the array from right to left while maintaining a decreasing stack. Use a variable to track the best candidate for the middle value (ak). If the current element becomes smaller than this stored value, a valid 132 pattern exists. Each element is processed once, resulting in O(n) time.
What is the best approach for 132 Pattern?
The most efficient approach uses a monotonic stack and scans the array from right to left. It tracks possible 'aj' values in a decreasing stack and stores the best candidate for 'ak' in a variable. This method detects a valid ai < ak < aj pattern in O(n) time with O(n) extra space.
Is 132 Pattern asked at Google/Amazon/Meta?
132 Pattern has appeared in interviews at major tech companies including Amazon, Google, and Meta. It tests knowledge of monotonic stacks, pattern detection in arrays, and the ability to optimize brute-force solutions into linear-time algorithms.
What data structure is used in 132 Pattern?
The optimal solution relies on a stack, specifically a monotonic decreasing stack. It helps maintain candidate values for the 'aj' element while tracking a valid 'ak' candidate during the backward scan of the array.
What is the time complexity of 132 Pattern?
The optimal stack-based solution runs in O(n) time because each element is pushed to and popped from the stack at most once. The brute force approach checks every triple (i, j, k) and requires O(n^3) time, which is impractical for large inputs.

Ready to solve this problem?

Practice 132 Pattern with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays