'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: 14 Feb, 2021

# Valid Stack Permutation

Moderate

## Problem statement

#### Example:

``````Consider array : 2 4 6.
Valid stack permutations are as follows:
2 4 6
push ‘2’
pop ‘2’
push ‘4’
pop ‘4’
push ‘6’
pop ‘6’
2 6 4
push ‘2’
pop ‘2’
push ‘4’
pop ‘6’
push ‘6’
pop ‘4’
4 2 6
push ‘2’
pop ‘4’
push ‘4’
pop ‘2’
push ‘6’
pop ‘6’
4 6 2
push ‘2’
pop ‘4’
push ‘4’
pop ‘6’
push ‘6’
pop ‘6’
6 4 2
push ‘2’
pop ‘4’
push ‘6’
pop ‘6’
push ‘4’
pop ‘6’

Now, If the other array is [2,4,6], [2,6,4], [4,2,6], [4,6,2], or [6,4,2] then the answer is “YES” otherwise “NO”.
``````
##### Note:
``````Please note that the arrays will only contain unique elements.
``````
##### Input Format:
``````The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case will contain an integer ‘N’ which represents the total number of elements in both arrays.

The second line of each test case contains the ‘N’ space-separated integers which represent the elements of the 'FIRST' array.

The third line of each test case contains the ‘N’ space-separated integers which represent the elements of the 'OTHER' array.
``````
##### Output Format:
``````For each test case, print “YES” if the first array is a valid stack permutation of the other. Otherwise, print “NO”.
``````
##### Note:
``````You don’t need to print anything; It has already been taken care of.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10000
0 <= FIRST[i], OTHER[i] <= 10^5

Where 'FIRST[i]' and 'OTHER[i]' denote the value of the i-th element of the input arrays.

Time limit: 1 sec
``````

## Approaches

### 01 Approach

Follow the order of elements in the first array by considering the push and pop operations.

The basic idea is to iterate through all the elements of the first array and push each element in a stack. You also have to pop the elements from the stack with respect to the occurrence of elements in the other array, so as to maintain the order of push and pop operations.

The Steps are as follows:

1. Make a stack to hold the elements, Let’s assume ‘ST’.
2. Make a pointer (say, ‘P’) which will point to the elements of the other array. Initialize it with 0.
3. Now, iterate through the ‘FIRST’ array.
• Push the ‘i’-th element into the stack.
• If ‘P’-th element of ‘OTHER’ Array is equal to the top element of the stack ‘ST’ then,
• Pop this element and increment the pointer ‘P’.
• Repeat the step b until ‘ST’ is not empty.
4. Now, if the stack is empty return true otherwise false.