Validate Stack Sequences

Given two arrays pushed and popped with the same distinct values, return true if they could be the result of some sequence of push and pop operations on an initially empty stack: values pushed in the order of pushed and popped in the order of popped. This is LeetCode 946.

Example 1
Input: pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]
Output: true
Explanation: push 1, 2, 3, 4, pop 4, push 5, pop 5, 3, 2, 1.
Example 2
Input: pushed = [1, 2, 3, 4, 5], popped = [4, 3, 5, 1, 2]
Output: false
Explanation: 1 cannot be popped before 2, since 2 is above it.

How to Think About It

Step 1: Just simulate

Use a real stack. Push the values in order, and pop whenever the stack's top is the next value we need to pop.

Step 2: Popping as early as possible is always safe

If the top equals the next value in popped, we must pop it now: pushing anything else on top of it would bury it, and it could not come out in time. So there is never a choice to make, and a greedy simulation is enough.

Step 3: The verdict

After all pushes (each followed by as many pops as possible), the sequence is valid exactly when the stack is empty.

Walkthrough

Example 1, step by step:

Simulation of pushed [1, 2, 3, 4, 5] and popped [4, 5, 3, 2, 1] with the stack after each step
PushedPopped right afterStack afterNext value to pop
1, 2, 3[1, 2, 3]4
44[1, 2, 3]5
55, 3, 2, 1[]done

For example 2, after popping 4, 3 and pushing and popping 5, the stack is [1, 2] with 2 on top, but the next value needed is 1. The stack is not empty at the end, so the answer is false.

Java Solution

next points at the next value in popped.

Java
import java.util.ArrayDeque;
import java.util.Deque;

public class ValidateStackSequences {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int next = 0; // next value of popped to produce
        for (int value : pushed) {
            stack.push(value);
            while (!stack.isEmpty() && stack.peek() == popped[next]) {
                stack.pop(); // pop as soon as the top is the value we need
                next++;
            }
        }
        return stack.isEmpty();
    }
}

The original implementation, ValidateStackSequences.java, is on GitHub.

Complexity

  • Time: O(n): each value is pushed and popped at most once.
  • Space: O(n) for the stack.

Simulating the structure itself is often the simplest check, as in Implement Stack using Queues.