Stack Permutations (Check if an array is stack permutation of other)

The problem, simply

You get two arrays of the same distinct numbers, A and B. Numbers from A arrive in order. You have one stack. At any moment you can push the next number of A onto the stack, or pop the top of the stack into the output. Can the output be exactly B?

If yes, B is a stack permutation of A. Return true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every possible plan. At each moment there are at most two choices: push the next car, or pop the top car. Explore both with backtracking, and when all cars have left, compare the output with B.

import java.util.*;

class Solution {
    public boolean isStackPermutation(int[] a, int[] b) {
        if (a.length != b.length) return false;
        return tryAll(a, b, 0, new ArrayDeque<>(), new ArrayList<>());
    }

    private boolean tryAll(int[] a, int[] b, int next, Deque<Integer> stack, List<Integer> out) {
        if (next == a.length && stack.isEmpty()) {          // every car has left
            for (int k = 0; k < b.length; k++) if (out.get(k) != b[k]) return false;
            return true;
        }
        if (next < a.length) {                              // choice 1: push the next car
            stack.push(a[next]);
            if (tryAll(a, b, next + 1, stack, out)) return true;
            stack.pop();
        }
        if (!stack.isEmpty()) {                             // choice 2: pop the top car
            int x = stack.pop();
            out.add(x);
            if (tryAll(a, b, next, stack, out)) return true;
            out.remove(out.size() - 1);
            stack.push(x);
        }
        return false;
    }
}

How long it takes: a plan is a string of n pushes and n pops, and there are up to about 4^n such strings to explore, O(4^n). Extra room: the stack, the output and the recursion are each O(n).

Way 2: the clever way

There is never a real choice. If the top of the stack is the next car B wants, popping it now is the only way it can ever leave in time. If it is not, the only thing you can do is push more.

1. Keep j, the position in B of the next car that must leave.
2. For each car x of A: push x.
3. While the stack is not empty and its top equals B[j]: pop and move j forward.
4. At the end, B is reachable exactly when the stack is empty.

import java.util.*;

class Solution {
    public boolean isStackPermutation(int[] a, int[] b) {
        if (a.length != b.length) return false;
        Deque<Integer> stack = new ArrayDeque<>();
        int j = 0;                                    // next car that must leave
        for (int x : a) {
            stack.push(x);                            // the car rolls into the siding
            while (!stack.isEmpty() && stack.peek() == b[j]) {
                stack.pop();                          // it is wanted now, send it out
                j++;
            }
        }
        return stack.isEmpty();                       // every car left in B's order
    }
}

How long it takes: each car is pushed once and popped at most once, O(n). Extra room: the stack can hold all n cars, O(n).

Watch out for

• Popping only once per push. After a pop, the new top might also be wanted. Use a while, not an if.
• Returning true when j reaches the end without checking lengths. Check a.length == b.length first.
• Repeated numbers. The greedy rule assumes distinct cars. With repeats, "the top equals the wanted value" may be true for the wrong copy, and the problem needs more care.

What interviewers ask next

• How many orders can come out of a stack for n cars? The Catalan number C(n) = (2n)! / ((n + 1)! n!): 1, 2, 5, 14, 42, ... Quant interviewers love this link.
• Which orders are impossible? Exactly those where some three cars leave in the shape big, small, middle, like 3, 1, 2. In grown-up words, the order contains the pattern 312.
• Validate push and pop sequences (LeetCode 946) is the same problem with pushed and popped arrays.
• Can two stacks in a row produce every order? No, but they produce many more. With a queue instead of a stack, only the same order A can come out.

Remember this

Grown-up words: the siding is a stack, a plan of pushes and pops is an operation sequence, B being reachable means it is a stack permutation, and popping as soon as possible is a greedy simulation.