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
- Simulate: push elements from
pushedone at a time, and after each push pop as many elements as match the current position inpopped. - If the simulation ends with an empty stack, the sequences are consistent.
- The greedy popping is safe because a distinct-valued stack has exactly one possible top at any moment.
- The
jpointer intopoppedmust 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 ofnot 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.