'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
Asked in companies
Paytm (One97 Communications Limited)HPC Sphere Pvt Ltd

Problem statement

You have been given two arrays having an equal number of elements. You have to find whether one array is the valid stack permutation of the other. An array is said to be a valid stack permutation of the other if and only if after applying some push and pop operations onto the sequence of elements in that array, will result in the other array.

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.