⚡Flashcard Drill➔
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

  1. Scan from right to left, maintaining a decreasing stack of candidates for the nums[j] (the middle element).
  2. Track third, the largest value that has been popped from the stack -- this is the best candidate for nums[k] (the rightmost element).
  3. If the current element is less than third, we have found nums[i] < nums[k] < nums[j].
  4. Otherwise, pop all smaller elements into third and 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 third with the wrong element: third must be the largest popped value, which is exactly the best nums[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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems