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

Difficulty Level Medium
Frequently asked in Amazon Fourkites
Combinatorial Queue StackViews 3621

Problem Statement

The problem “Stack Permutations (Check if an array is stack permutation of other)” states that you are given two arrays a[ ] and b[ ] of size n. All the elements of the array are unique. Create a function to check if the given array b[ ] is the stack permutation of given array a[ ] or not.

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

Example

a[ ] = {1, 2, 3}

b[ ] = {2, 1, 3}
Yes

Explanation: First push 1 and 2 into the stack. Then pop them from the stack. Afterward, push 3, then pop 3. So the resultant sequence looks something like 2, 1,3 which is our second array.

a[ ] = {1, 2, 3}

b[ ] = {3, 1, 2}
No

Explanation: There is no sequence of push and pop that will result into the second array. And thus answer is NO.

Algorithm

  1. Initialize two arrays a[ ] and b[ ] of size n.
  2. Create a function to check stack permutation which accepts the two integer arrays and the size of the array as it’s parameters.
  3. After that, create a queue data structure of integer type.
  4. Traverse through the array a[ ] and push/insert all the elements of the array a[ ] in the queue.
  5. After that, create a second queue data structure of integer type.
  6. Traverse through the array b[ ] and push/insert all the elements of array b[ ] in the queue.
  7. Similarly, create a stack data structure of integer type.
  8. Traverse while the size of the first queue is not 0. Create an integer variable and store the element at the front of the first queue in it and pop/remove it from the first queue.
  9. Check if the value in the integer variable is not equal to the element at the front of the second queue, push/insert the integer variable in the stack.
  10. Else pop/remove the element at the front of the second queue.
  11. Traverse again while the size of the stack is not 0. Check if the element at the top of the stack is equal to the element at the front of the second queue, pop / remove the element at the front of the second queue, and from the top of the stack. Else break.
  12. Check if both the stack and the first queue are empty, print “Yes” else print “No”.

Code

C++ Program for Stack Permutations

#include<bits/stdc++.h> 
using namespace std; 
  
bool checkStackPermutation(int a[], int b[], int n){ 
    
    queue<int> input; 
    for(int i=0; i<n; i++){ 
        input.push(a[i]);
    }
  
    queue<int> output; 
    for(int i=0; i<n; i++){ 
        output.push(b[i]);
    }
  
    stack <int> tempStack; 
    while(!input.empty()){ 
        int ele = input.front(); 
        input.pop(); 
        
        if (ele == output.front()){ 
            output.pop(); 
            
            while(!tempStack.empty()){ 
                
                if(tempStack.top() == output.front()){ 
                    tempStack.pop(); 
                    output.pop(); 
                } 
                
                else{
                    break;
                }
            } 
        } 
        else{
            tempStack.push(ele); 
        }
    } 
  
    return (input.empty()&&tempStack.empty()); 
} 
  
int main(){ 
    int a[] = {1, 2, 3}; 
    int b[] = {2, 1, 3}; 
  
    int n = sizeof(a)/sizeof(a[0]); 
  
    if(checkStackPermutation(a, b, n)){ 
        cout << "Yes"; 
    }
    else{
        cout << "No"; 
    }
    return 0; 
}
Yes

Java Program for Stack Permutations

import java.util.LinkedList; 
import java.util.Queue; 
import java.util.Stack; 
  
class StackPermutation{ 
    static boolean checkStackPermutation(int a[], int b[], int n){ 
        Queue<Integer> input = new LinkedList<>(); 
  
        for(int i = 0; i < n; i++){ 
            input.add(a[i]); 
        } 
  
        Queue<Integer> output = new LinkedList<>(); 
        for(int i = 0; i < n; i++){ 
            output.add(b[i]); 
        } 
  
        Stack<Integer> tempStack = new Stack<>(); 
        while(!input.isEmpty()){ 
            int ele = input.poll(); 
  
            if(ele == output.peek()){ 
                output.poll(); 
                
                while(!tempStack.isEmpty()){ 
                    
                    if(tempStack.peek() == output.peek()){ 
                        tempStack.pop(); 
                        output.poll(); 
                    } 
                    
                    else{
                        break;
                    }
                } 
            }  
            else{ 
                tempStack.push(ele); 
            } 
        } 
  
        return (input.isEmpty() && tempStack.isEmpty()); 
    } 
  
    public static void main(String[] args){ 
        
        int a[] = { 1, 2, 3 }; 
        int b[] = { 2, 1, 3 }; 
        int n = a.length;
        
        if(checkStackPermutation(a, b, n)){ 
            System.out.println("Yes"); 
        }
        else{
            System.out.println("No"); 
        }
    } 
}
Yes

Complexity Analysis

Time Complexity

O(n) where n is the number of elements in a given array a[ ] and b[ ]. We have just traversed through the array elements and thus a linear time complexity.

Space Complexity

O(n) because we used space for n elements. We created two queues and stack which makes the algorithm to have linear complexity in space.

Translate ยป