Course4all
Join us on telegram
Home/dsa/Stack/Validate Stack Sequences

Validate Stack Sequences

Master this topic with zero to advance depth.

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.

← Previous QuestionOnline Stock Span
Next Question →Basic Calculator II