Valid Stack Permutation

Moderate
0/80
Average time to solve is 45m
profile
Contributed by
23 upvotes
Asked in company
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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
2 4 6
4 6 2
3
2 4 6
6 2 4
Sample Output 1:
YES
NO
Explanation of Sample Output 1:
In test case 1, The explanation is already given in the example.

In test case 2, The explanation is already given in the example.
Sample Input 2:
2
3
2 4 6
2 3 4
1
5
5
Sample Output 2:
NO
YES
Explanation for Sample Output 2:
In test case 1, the 'FIRST' array does not contain 3 but the 'OTHER' array contains 3. So, the other is not the valid stack permutation.

In test case 2, the only array containing ‘5’ as an element is the valid stack permutation of the array [5].
Hint

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

Approaches (1)
Using Stack

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.
Time Complexity

O(N), Where ‘N’ is the length of the given arrays.

 

Since we are iterating through the array once the worst-case time complexity will be O(N). We are here only doing N push/pop operations because of that the overall time complexity will be O(N).

Space Complexity

O(N)

 

Since we are storing each element in a stack which results in O(N) space complexity in the worst case. So, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Valid Stack Permutation
Full screen
Console