Validate Stack Sequences

Medium
387.

Validate Stack Sequences

Validate Stack Sequences is a medium coding problem on arrays, simulation and stack, asked in Amazon, Google, Microsoft and Sprinklr interviews.

Given two integer arrays pushed and popped, each a permutation of the other with distinct values, return true if they could be the push and pop sequences of one initially empty stack.

Example 1

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

Example 2

Input
pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output
false
Explanation
1 cannot be popped before 2.

Example 3

Input
pushed = [1], popped = [1]
Output
true

Constraints

  • 1 <= pushed.length <= 30
  • popped.length == pushed.length
  • The two arrays are permutations of each other with distinct values.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Validate Stack Sequences — Solution in Python, Java & C++

Validate Stack Sequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Validate Stack Sequences is a medium coding problem on arrays, simulation and stack, asked in Amazon, Google, Microsoft and Sprinklr interviews.

Problem statement

Given two integer arrays pushed and popped, each a permutation of the other with distinct values, return true if they could be the push and pop sequences of one initially empty stack.

Example 1

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

Example 2

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Example 3

Input: pushed = [1], popped = [1]
Output: true

Constraints

  • 1 <= pushed.length <= 30
  • popped.length == pushed.length
  • The two arrays are permutations of each other with distinct values.

Hints for Validate Stack Sequences

  1. Hint 1

    Simulate: push the values in order, and after each push, pop greedily while the top matches the next value to pop.

  2. Hint 2

    The greedy pop is forced — if the top equals the next expected pop and you do not pop it now, you never can.

  3. Hint 3

    The sequences are valid exactly when the stack ends empty.

How to solve Validate Stack Sequences

Simulate: push in order and, after each push, pop greedily while the top matches the next expected pop. The sequences are valid iff the stack ends empty.

Approach

  1. For each x in pushed, push it, then pop while top == popped[j], advancing j.
  2. Return whether the stack is empty.

Why it works

If the top equals the next value to pop and you do not pop it now, it becomes buried and can never be popped in the right order, so the greedy pop is forced and the simulation is exact.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Values are distinct, so matching by value is unambiguous.

Reference solution

Python

def validateStackSequences(pushed, popped) -> bool:
    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 len(stack) == 0

Java

public static 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 stack.isEmpty();
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure