AlgoMaster Logo

Validate Stack Sequences

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're given two arrays that represent the order in which elements were pushed onto a stack and the order in which they were popped off. Our job is to determine whether the pop sequence is achievable given the push sequence.

A stack is last-in-first-out (LIFO). Once you push elements 1, 2, 3, you can only pop 3 first, not 1 or 2. But you don't have to push everything before you start popping. You can interleave pushes and pops in any order, as long as you respect the push order and the LIFO constraint.

At any point during the simulation, the only element you can pop is whatever is currently on top of the stack. This lets us simulate the process greedily: push elements in the given order, and whenever the stack's top matches the next element we need to pop, pop it.

Key Constraints:

  • 1 <= pushed.length <= 1000 → With n up to 1000, even an O(n^2) approach stays within about a million operations. An O(n) solution exists, so we aim for that.
  • All elements of pushed are unique → Since every value appears exactly once, there's no ambiguity about which element we're matching when we pop. Each value in the popped array corresponds to exactly one push.
  • popped is a permutation of pushed → We're guaranteed the same set of elements. We don't need to worry about missing or extra values.

Approach 1: Brute Force (Try All Interleavings)

Intuition

At each step, we have two choices. We can push the next element from the pushed array, or we can pop the top of the stack (if it matches the next element in the popped array). We can explore all possible interleavings of pushes and pops to see if any of them produce the desired pop sequence.

This is essentially a decision tree. At each step, branch into "push" and "pop" (when valid), and see if any path through the tree results in the full popped sequence being satisfied.

Algorithm

  1. Start with an empty stack, a pointer into pushed (at index 0), and a pointer into popped (at index 0).
  2. At each step, try two options:
    • Push the next element from pushed (if there are elements left to push).
    • Pop the top of the stack (if the stack is non-empty and the top matches popped[popIndex]).
  3. Recursively explore both branches.
  4. If the pop pointer reaches the end (all elements have been popped in order), return true.
  5. If no branch leads to a valid sequence, return false.

Visualization and Code

Loading animation...

The bottleneck is the exponential branching. The next approach removes it by collapsing the two choices into one: whenever the stack top matches the next expected pop, pop it, without exploring the alternative.

Approach 2: Greedy Stack Simulation

Intuition

Instead of exploring all interleavings, we commit to one rule: whenever the top of the stack matches the next element we need to pop, pop it immediately.

This greedy choice is safe because the push order is fixed. If the top of the stack is the value we need to pop next and we push more elements instead, those new elements sit on top and must all be popped before we can reach the one we need. The element we wanted is still on top after that detour, so popping it now can never make a later step impossible. Delaying the pop only adds work.

The algorithm follows directly: push elements one at a time in the given order, and after each push, keep popping while the top matches the next expected pop. If we get through all pushes and all pops, the sequence is valid.

Algorithm

  1. Initialize an empty stack and a pointer popIdx at 0 (pointing to the first element of popped).
  2. Iterate through each element in pushed:
    • Push the current element onto the stack.
    • After pushing, check: while the stack is non-empty and the top equals popped[popIdx], pop and increment popIdx.
  3. After processing all pushes, if popIdx equals the length of popped, return true. Otherwise, return false.

Visualization and Code

Loading animation...

The time complexity is already optimal. The remaining cost is the O(n) extra space for the stack, which the next approach removes by reusing the input array itself.

Approach 3: In-Place Simulation (O(1) Extra Space)

Intuition

The greedy simulation from Approach 2 is already O(n) in time. The only thing left to optimize is space. As we iterate through pushed, we're reading elements from the left and we've already processed them. Those positions in the pushed array are "free."

So instead of maintaining a separate stack, we can reuse the pushed array itself. We keep a pointer top that represents the top of our "virtual stack" within the pushed array. When we push, we write the value at pushed[top] and increment top. When we pop, we decrement top.

Algorithm

  1. Initialize top = 0 (this acts as the stack pointer within the pushed array) and popIdx = 0.
  2. For each element val in pushed:
    • Write val at pushed[top] and increment top. (This "pushes" onto our virtual stack.)
    • While top > 0 and pushed[top - 1] == popped[popIdx], decrement top and increment popIdx. (This "pops" from our virtual stack.)
  3. Return top == 0 (if the virtual stack is empty, all elements were matched).

Visualization and Code

Loading animation...