Validate Stack Sequences

medium stack simulation array

Problem

Given two integer sequences pushed and popped, each a permutation of the same distinct values, return true if and only if this could be the result of a sequence of push and pop operations on an initially empty stack.

Inputpushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]

Outputtrue

Push 1,2,3,4 then pop 4, push 5 then pop 5, then pop 3,2,1 in order.

pushed (comma-separated)

popped (comma-separated)

def validate_stack_sequences(pushed, popped):
    stack = []
    j = 0
    for x in pushed:
        stack.append(x)
        while stack and j < len(popped) and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return j == len(popped)

function validateStackSequences(pushed, popped) {
  const stack = [];
  let j = 0;
  for (const x of pushed) {
    stack.push(x);
    while (stack.length && j < popped.length && stack[stack.length - 1] === popped[j]) {
      stack.pop();
      j++;
    }
  }
  return j === popped.length;
}

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }
}

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> st;
    int j = 0;
    for (int x : pushed) {
        st.push(x);
        while (!st.empty() && j < (int)popped.size() && st.top() == popped[j]) {
            st.pop();
            j++;
        }
    }
    return j == (int)popped.size();
}

Explanation

The cleanest way to know if a push/pop order is achievable is to simulate it with a real stack and a greedy rule: push values in the given order, and pop as soon as the top matches the next value we are supposed to pop.

We keep a pointer j into popped. For each value in pushed, we push it, then run a while loop: as long as the stack's top equals popped[j], we pop it and advance j. Greedily popping whenever we can is always safe, because a value that can come off now will never have a better chance later.

After every push has been processed, the sequence is valid exactly when j reached the end of popped — meaning every pop request was satisfied in order. If items are stuck on the stack, the order was impossible.

Example: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]. Push 1,2,3,4; top is 4 = popped[0], pop it. Push 5; top 5 = next pop, pop it. Now 3,2,1 sit with 3 on top, matching the remaining pops in order, so all get popped and j reaches the end → true.

Each value is pushed once and popped at most once, so the simulation runs in linear time.

Time: O(n) Space: O(n)