Stack Permutation

#geeksforgeeks #algorithms #stack #solution

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,

stack underflow, or
output array iteration completed but stack still empty or
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;
    }
}

Top comments (1)

𒎏Wii 🏳️‍⚧️ • Sep 7 '22 • Edited

A = {1,2,3}
B = {3,1,2}
move 1 from A to C
move 2 from A to C
move 3 from A to B
move 2 from C to A
move 1 from C to B
move 2 from A to B

I think you're missing some constraint here, because the way you described it, any permutation of the items in A can be recreated in B using an auxiliary stack.

A quick look at wikipedia clarified the problem: You're talking about arrays, but that makes the solution trivial because you can push elements back into an array and basically just move back and forth seeking the elements you want. For the problem to work, both input and output have to be defined as streams, where you get one element at a time and can't put it back.

And with that figured out, here's my quick and dirty solution in Lua:

local function sortable(A, B)
    local S = {}
    local pos_B = 1
    for i, v in ipairs(A) do
        table.insert(S, v)
        while S[#S] and S[#S] == B[pos_B] do
            table.remove(S)
            pos_B = pos_B + 1
        end
    end
    return #S == 0
end

print(sortable({1, 2, 3}, {2, 1, 3}))
print(sortable({1, 2, 3}, {3, 1, 2}))

DEV Community

Stack Permutation

Problem Statement

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(N)

Solution

Top comments (1)

Read next

Understanding the Importance of @Injectable in NestJS

An In-Depth Objective Review of JUMP By Cognixia’s Python Program

Simplifying Your Workflow: npm run vs npm --run

Salesforce Clouds Overview