⚡Flashcard Drill➔
NeetCode #353LC-946MediumStack
← Back to All Problems

#353 · #946 · Validate Stack Sequences(验证栈序列)

📌 Problem Statement & Constraints

Given two integer arrays pushed and popped representing the push and pop sequences of a stack, return true if they could have been produced by a valid sequence of stack operations. All values are distinct. Constraints: 1 <= pushed.length == popped.length <= 1000.

💡 Core Algorithmic Approaches

  1. Simulate: push elements from pushed one at a time, and after each push pop as many elements as match the current position in popped.
  2. If the simulation ends with an empty stack, the sequences are consistent.
  3. The greedy popping is safe because a distinct-valued stack has exactly one possible top at any moment.
  4. The j pointer into popped must be bounds-checked, since it can reach the end before the loop finishes.

💻 Benchmark Python3 Implementation

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st = []
        j = 0
        for x in pushed:
            st.append(x)
            # pop while the top matches the next expected output
            while st and j < len(popped) and st[-1] == popped[j]:
                st.pop()
                j += 1
        return not st                      # everything must have been popped

⚡ 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

  • Forgetting the j < len(popped) guard: the index would run past the end once all elements have been matched.
  • Popping only once per push: a single push can trigger a cascade of pops.
  • Checking j == len(popped) instead of not st: both work given equal lengths, but the empty-stack test is the direct statement of correctness.
  • Assuming values can repeat: the problem guarantees distinct values, which is what makes the greedy unambiguous.
⚡
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