Stack: Given 2 arrays, check if an array is stack permutation of another

Problem Statement:

You are given 2 array of same size and the elements are unique.

You need to check if a[] is a stack permutation of b[].

You need to assume a[] as the input array and b[] as output array.

The input array, only dequeue operation is permitted.

You are allowed to take a stack in which push and pop operation is allowed.

Stack and input queue should be empty at the end.

To sum-up, below are the operations allowed:

1. Only dequeue from input stack.

2. Push and pop operations from the stack.

3. Only enqueue operation to output stack

4. Stack and queue should be empty at the end

Example:

Input: a[] = [1, 2, 3, 4]
b [] = [4, 3, 2, 1]

Output: True.

Explanation:

If we pop the elements from a[], we will get b[]

Solution Explanation:

Take empty stack.

Push the element of the first array into the stack one by one.

Once pushed, check if the top of the stack matches the current element of b[].

if yes, then pop from the stack and move to next element of b[].

Repeat the steps till all the element of a[] are pushed.

At the end check if all the elements of b[] should be popped, then return 0.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

bool solution(vector<int>& pushed, vector<int>& popped) 
{
    stack<int> s ; 
    int j = 0;
    for(int i= 0; i<pushed.size(); ++i)
    {
        s.push(pushed[i]);
        
        while(!s.empty() && s.top() == popped[j])
        {
            s.pop();
            ++j;
        }
    }
    return s.empty();
}


int main() {
    vector<int> a = {1, 2, 3};
    vector<int> b = {3, 2, 1};

    cout << (solution(a, b) ? "True" : "False") << endl;

    return 0;
}

Output

True