MediumNo. 0456
132 Pattern — LeetCode 456 Python Solution
- Pattern
- Stack
- Topics
- Stack, Array, Binary Search, Ordered Set, Monotonic Stack
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [1,2,3,4]
- Output
- false
- Explanation
- There is no 132 pattern in the sequence.
Python solution
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
vk = -inf
stk = []
for x in nums[::-1]:
if x < vk:
return True
while stk and stk[-1] < x:
vk = stk.pop()
stk.append(x)
return FalseComplexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 456. 132 Pattern is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2454 | Next Greater Element IV | Hard |
| 2736 | Maximum Sum Queries | Hard |
| 2940 | Find Building Where Alice and Bob Can Meet | Hard |
| 2945 | Find Maximum Non-decreasing Array Length | Hard |
| 0084 | Largest Rectangle in Histogram | Hard |
| 0315 | Count of Smaller Numbers After Self | Hard |
Frequently asked questions
- How hard is LeetCode 456. 132 Pattern?
LeetCode 456. 132 Pattern is rated Medium on LeetCode.
- What topics does LeetCode 456. 132 Pattern cover?
LeetCode 456. 132 Pattern is tagged Stack, Array, Binary Search, Ordered Set and Monotonic Stack on LeetCode.