Check if an array is a valid stack permutation of another
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
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;}