Domain 2MediumMEDIUM

Validate Stack Sequences

Simulate stack operations by pushing elements from 'pushed' and popping when the top matches 'popped'. Return true if all elements are popped in order.

Domain: medium•Updated: 2026-09-04
#simulation#stack#O(N) time complexity#O(N) space complexity

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 NN. Values are distinct.

Outputs:

  • Boolean: True if valid, False otherwise.

Intuition

A brute-force approach exploring all push/pop combinations is exponential (O(2N)O(2^N)). 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

  1. Initialize an empty stack and a pointer j for the current element required from popped.
  2. Iterate through each number in pushed:
    • Push the number onto our simulated stack.
  3. 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 j to look for the next required element in popped.
  4. 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: O(N)O(N) where NN is the length of pushed. Each element from pushed enters 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: O(N)O(N) 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 (N=0N=0), the loop over pushed does not execute. Stack remains empty. Returns True, 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 popped order or were covered by later pushes. Returns False.
  • Distinct Values Constraint: Simplifies logic as we don’t need to handle duplicate value ambiguity (e.g., which ‘2’ is being matched).