Problem Breakdown
We need to determine if popped is a valid permutation of pushed achievable via stack operations. The core constraint is the Last-In, First-Out (LIFO) property of stacks. We cannot access an element buried in the stack without popping all elements above it first. Since values are distinct, we can uniquely identify which instance of a value corresponds to the current operation.
Inputs:
pushed: List[int] - The sequence of items entering the stack.popped: List[int] - The desired exit order from the stack.- Both lists have equal length . Values are distinct.
Outputs:
- Boolean: True if valid, False otherwise.
Intuition
A brute-force approach exploring all push/pop combinations is exponential (). Instead of guessing operations, we simulate the process deterministically based on popped. The element currently required by popped (at index j) must be at the top of our stack to be popped. If it isn’t there yet, we must push elements from pushed until that specific value appears or runs out of items in pushed. Once a match is found on top, we pop immediately because leaving it covered by future pushes would make it impossible to retrieve before those new elements if they are needed later.
Approach
- Initialize an empty stack and a pointer
jfor the current element required frompopped. - Iterate through each number in
pushed:- Push the number onto our simulated stack.
- After every push, check if we can pop:
- While the stack is not empty AND the top of the stack equals
popped[j]:- Pop from the stack.
- Increment pointer
jto look for the next required element inpopped.
- While the stack is not empty AND the top of the stack equals
- After processing all elements in
pushed, check if the stack is empty:- If empty, every pushed item was successfully popped in the correct order -> Return True.
- If not empty, some items remain trapped below others or were never matched correctly -> Return False.
Complexity Analysis
- Time: where is the length of
pushed. Each element frompushedenters the stack exactly once and leaves at most once. The inner while loop processes each pop operation, which corresponds to an exit event for a specific element. Total operations are linear relative to input size. - Space: in the worst case (e.g., all elements pushed before any pops occur).
Solution
def validateStackSequences(pushed: list[int], popped: list[int]) -> bool:
"""
Determines if 'popped' is a valid sequence of pop operations
given that elements are pushed in the order specified by 'pushed'.
Args:
pushed (List[int]): Sequence of values entering the stack.
popped (List[int]): Desired sequence leaving the stack.
Returns:
bool: True if valid, False otherwise.
"""
stack = []
pop_idx = 0
# Iterate through every element that gets pushed onto our simulated stack
for num in pushed:
stack.append(num)
# Greedy check: If the top of the stack matches what we need to pop next,
# perform the pop immediately. This is mandatory because leaving it on
# the stack would cover any subsequent elements needed before this one.
while stack and stack[-1] == popped[pop_idx]:
stack.pop()
pop_idx += 1
# If the stack is empty, all pushed items were successfully matched to popped sequence.
return len(stack) == 0
# Example usage:
print(validateStackSequences([1,2,3,4,5], [4,5,3,2,1])) # True
print(validateStackSequences([1,2,3,4,5], [4,3,5,1,2])) # False
Edge Cases Handled
- Empty Arrays: If both lists are empty (), the loop over
pusheddoes not execute. Stack remains empty. ReturnsTrue, which is correct as no operations were needed to satisfy an empty sequence condition. - Single Element: Pushes one item, checks match immediately against
popped. If valid[1] -> [1], returns True; otherwise False (though constraints imply permutation so this implies equality). - Impossible Pop Order: The stack will contain elements at the end that were pushed but never popped because they didn’t match
poppedorder or were covered by later pushes. ReturnsFalse. - Distinct Values Constraint: Simplifies logic as we don’t need to handle duplicate value ambiguity (e.g., which ‘2’ is being matched).