Stack Permutations (Check if an Array is a Stack Permutation of Another)

In this article, we will solve the problem of checking if one array is a stack permutation of another.

Problem Statement: A stack permutation involves reordering elements from the given input queue using a stack, following the rules of stack operations (push and pop). Given two arrays of unique elements, the task is to determine if the second array is a valid stack permutation of the first array.

Rules:

1.    Elements can only be removed from the front of the input queue.

2.    Use stack operations (push and pop) to transfer elements between the input and output queues.

3.    Both the stack and the input queue must be empty at the end.

4.    Elements can only be added to the end of the output queue.

Example:

Input: arr1 = [4, 5, 6], arr2 = [5, 4, 6] Output: YES

Explanation:

1.    Push 4 from input to stack.

2.    Push 5 from input to stack.

3.    Pop 5 from stack to output.

4.    Pop 4 from stack to output.

5.    Push 6 from input to stack.

6.    Pop 6 from stack to output.

Solution:

To determine if the second array is a stack permutation of the first array, we will use a stack to simulate the process.

Steps to Solve:

1.    Initialize the Stack and Index Variables:

o   Create an empty stack.

o   Initialize an index variable for the output array.

2.    Iterate Through the Input Array:

o   For each element in the input array:

§  Push the element onto the stack.

§  While the stack is not empty and the top of the stack matches the current element in the output array:

§  Pop the element from the stack.

§  Move to the next element in the output array.

3.    Check if the Output Array is Fully Processed:

o   If the index variable for the output array equals the length of the output array, return YES.

o   Otherwise, return NO.

Time Complexity: O(N)

Space Complexity: O(N)