Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 14 Feb, 2021

Moderate

```
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”.
```

```
Please note that the arrays will only contain unique elements.
```

```
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.
```

```
For each test case, print “YES” if the first array is a valid stack permutation of the other. Otherwise, print “NO”.
```

```
You don’t need to print anything; It has already been taken care of.
```

```
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
```

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:

- Make a stack to hold the elements, Let’s assume ‘ST’.
- Make a pointer (say, ‘P’) which will point to the elements of the other array. Initialize it with 0.
- 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.

- Now, if the stack is empty return true otherwise false.

Similar problems

Postorder Traversal

Easy

Posted: 20 Jan, 2022

Postorder Traversal

Easy

Posted: 20 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Min Stack

Easy

Posted: 22 Jan, 2022

Stock Span

Moderate

Posted: 16 Jun, 2022

Stock Span

Moderate

Posted: 16 Jun, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Hills and Soldier

Moderate

Posted: 7 Jul, 2022

Next Greater Element II

Moderate

Posted: 9 Sep, 2022