132 Pattern — Solution in Python, Java & C++
132 Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
132 Pattern is a medium coding problem on arrays, binary search and stack, asked in Amazon, Google, Bloomberg and Sprinklr interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Stack, Monotonic Stack, Ordered Set
- Asked at: Amazon, Google, Bloomberg, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A 132 pattern is a subsequence nums[i], nums[j], nums[k] with i < j < k and nums[i] < nums[k] < nums[j].
Given an integer array nums, return true if such a pattern exists.
Example 1
Input: nums = [1,2,3,4]
Output: false
Explanation: The array is increasing.
Example 2
Input: nums = [3,1,4,2]
Output: true
Explanation: 1, 4, 2 is a 132 pattern.
Example 3
Input: nums = [-1,3,2,0]
Output: true
Constraints
1 <= nums.length <= 40-1000000000 <= nums[i] <= 1000000000
Hints for 132 Pattern
Hint 1
Scan from the right and maintain a decreasing stack of candidates for the
3.Hint 2
Whenever a value pops elements off the stack, those popped values are valid candidates for the
2— keep the largest one seen.Hint 3
If the current element is smaller than that best
2, you have found the1and the pattern exists.
How to solve 132 Pattern
Scan from the right with a decreasing stack of candidates for the 3; values popped by a larger element are candidates for the 2 — keep the largest — and any element smaller than that is the 1.
Approach
- For
xfrom right to left: ifx < third, returntrue. - While the stack top is less than
x, pop it intothird. - Push
x.
Why it works
third is always the largest value that has a larger element to its right (the 3 that popped it), so the first x below third completes a 1 < 2 < 3 pattern with i < j < k.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Initialise
thirdto-∞so nothing matches before a real2exists.
Reference solution
Python
def find132pattern(nums) -> bool:
stack = []
third = float("-inf")
for x in reversed(nums):
if x < third:
return True
while stack and stack[-1] < x:
third = stack.pop()
stack.append(x)
return FalseJava
public static boolean find132pattern(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
boolean hasThird = false;
int third = 0;
for (int i = nums.length - 1; i >= 0; i--) {
if (hasThird && nums[i] < third) return true;
while (!stack.isEmpty() && stack.peek() < nums[i]) {
third = stack.pop();
hasThird = true;
}
stack.push(nums[i]);
}
return false;
}C++
bool find132pattern(vector<int>& nums) {
vector<int> stack;
bool hasThird = false;
int third = 0;
for (int i = (int) nums.size() - 1; i >= 0; i--) {
if (hasThird && nums[i] < third) return true;
while (!stack.empty() && stack.back() < nums[i]) {
third = stack.back();
stack.pop_back();
hasThird = true;
}
stack.push_back(nums[i]);
}
return false;
}JavaScript
var find132pattern = function(nums) {
const stack = [];
let third = -Infinity;
for (let i = nums.length - 1; i >= 0; i--) {
if (nums[i] < third) return true;
while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
third = stack.pop();
}
stack.push(nums[i]);
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search