Course4all

Validate Stack Sequences

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Stack.

Validate Stack Sequences

Determine if a sequence of indices popped could have resulted from a sequence of pushed operations on an empty stack.

Visual Representation

pushed = [1, 2, 3], popped = [2, 3, 1] 1. Push 1: Stack [1] 2. Push 2: Stack [1, 2]. Top 2 == popped[0]. Pop. Stack [1] 3. Push 3: Stack [1, 3]. Top 3 == popped[1]. Pop. Stack [1] 4. No more pushes. Top 1 == popped[2]. Pop. Stack [] Result: True
Medium

Examples

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Approach 1

Level I: Brute Force (Try All Push/Pop Orders)

Intuition

Without insight, we could try all possible sequences of push/pop operations on pushed[] to check if any of them matches popped[]. However, given that each element must be pushed exactly once, the simulation approach is actually already optimal in practice. The 'brute force' here is to consider a naive simulation without the greedy insight.
⏱ O(N) — same as the optimal, as the greedy simulation is the most natural approach.💾 O(N) for the stack.
java
import java.util.Stack;

public class Main {
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIdx = 0;
        for (int val : pushed) {
            stack.push(val);
            // Pop as much as possible
            while (!stack.isEmpty() && stack.peek() == popped[popIdx]) {
                stack.pop();
                popIdx++;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) {
        System.out.println(validateStackSequences(new int[]{1,2,3}, new int[]{2,3,1}));
    }
}
Approach 2

Level III: Optimal (Greedy Simulation)

Intuition

Iterate through the pushed array and push each element onto a stack. After each push, greedily pop elements from the stack as long as the stack top matches the current element in the popped array.
⏱ O(N)💾 O(N)

Detailed Dry Run

PushStackPopped PointerAction
1[1]0Push
2[1, 2]0Push
-[1]1 (2 matched)Pop
3[1, 3]1Push
-[]3 (3 then 1 matched)Pop, Pop
java
import java.util.*;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validateStackSequences(new int[]{1,2,3}, new int[]{2,3,1})); // true
    }
}

⚠️ Common Pitfalls & Tips

All elements in pushed and popped are distinct as per standard constraints. Ensure you pop as many matching elements as possible after each push.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionOnline Stock Span
Next Question →Basic Calculator II