NeetCode #372LC-456MediumStack
← Back to All Problems#372 · #456 · 132 Pattern(132 模式)
📌 Problem Statement & Constraints
Given an array of
n integers nums, return true if there is a 132 pattern: indices i < j < k with nums[i] < nums[k] < nums[j]. Constraints: 1 <= n <= 2 * 10^5, -10^9 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Scan from right to left, maintaining a decreasing stack of candidates for the
nums[j](the middle element). - Track
third, the largest value that has been popped from the stack -- this is the best candidate fornums[k](the rightmost element). - If the current element is less than
third, we have foundnums[i] < nums[k] < nums[j]. - Otherwise, pop all smaller elements into
thirdand push the current one.
💻 Benchmark Python3 Implementation
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
st = [] # decreasing candidates for nums[j]
third = float("-inf") # best candidate for nums[k]
for n in reversed(nums):
if n < third:
return True # found nums[i] < nums[k] < nums[j]
while st and st[-1] < n:
third = st.pop() # a better nums[k] candidate
st.append(n)
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Scanning left to right: the pattern's structure is much easier to exploit from the right.
- Updating
thirdwith the wrong element:thirdmust be the largest popped value, which is exactly the bestnums[k]. - Comparing
n <= third: the inequalities are strict, so equality does not form a 132 pattern. - Trying a triple nested loop: O(n^3).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.