Check if an array is a valid stack permutation of another

Medium

Problem

Elements of the input array are pushed onto a stack in order, and you may pop at any time. Return true if the output array can be produced as the sequence of popped values.

Example 1

Input:  input = [1, 2, 3], output = [2, 1, 3]
Output: true

Example 2

Input:  input = [1, 2, 3], output = [3, 1, 2]
Output: false

Also asked as: Stack Permutations (Check if an array is stack permutation of other)

Test cases

Case 1

Input:    [1,2,3], [2,1,3]
Expected: true

Case 2

Input:    [1,2,3], [3,1,2]
Expected: false

Case 3

Input:    [1,2,3], [3,2,1]
Expected: true

Case 4

Input:    [], []
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Simulate with an auxiliary stack

Time O(n)Space O(n)

Push input elements one by one; whenever the stack top equals the next expected output element, pop. If the stack empties out matching the whole output, it is a valid permutation.

function isStackPermutation(input, output) {
const st = [];
let j = 0;
for (const x of input) {
st.push(x);
while (st.length && st[st.length - 1] === output[j]) { st.pop(); j++; }
}
return st.length === 0 && j === output.length;
}