Problem Statement

You are given two arrays A and B of unique elements of size N. Check if one array is a stack permutation of the other array or not.
Stack permutation means that one array can be created from another array using a stack and stack operations.

Link to the problem statement:: https://practice.geeksforgeeks.org/problems/stack-permutations/1

Example 1:

Input:
N = 3
A = {1,2,3}
B = {2,1,3}
Output:
1
Explanation:
1. push 1 from A to stack
2. push 2 from A to stack
3. pop 2 from stack to B
4. pop 1 from stack to B
5. push 3 from A to stack
6. pop 3 from stack to B

Example 2:

Input:
N = 3
A = {1,2,3}
B = {3,1,2}
Output:
0
Explanation:
Not Possible

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(N)

Solution

How could a stack permutation be checked when you have input and output, the best way is to replicate the stack itself and enter the input.

Also while entering input, if any occurrence of output comes in we as the output needs to stimulate the stack ie, pop out the element. This needs to be done. While performing these operations whenever we encounter any illegal operation like,

1. stack underflow, or
2. output array iteration completed but stack still empty or
3. stack top and output array iteration point does not match and there is no other input operation that could make use believe that there might come a situation validating the permutation.

In these invalid cases, there is a clear answer indicating this permutation is not possible. When you see there is no more element in stack and output are is satisfied till the end, it is an indication you have achieved your permutation.

class Solution {
    public static int isStackPermutation(int n, int[] ip, int[] op) {
        Stack<Integer> stack = new Stack<>();
        int opItr = 0;
        for(int i = 0; i < ip.length; i++) {
            while(opItr < op.length && !stack.isEmpty() && stack.peek() == op[opItr]) {
                stack.pop();
                opItr++;
            }
            stack.push(ip[i]);
        }
        while((opItr < n) && !stack.isEmpty() && (stack.peek() == op[opItr])) {
            opItr++;
            stack.pop();
        }
        return (opItr == n && stack.isEmpty())? 1 : 0;
    }
}