Stacks & QueuesProblem 22 of 38
Stack Permutations (Check if an array is stack permutation of other)
Problem Statement
Given two arrays, both containing unique elements. Check if one array is a stack permutation of the other. An array B is a stack permutation of array A if it can be obtained by pushing elements of A onto a stack and popping them in a different order.
Example:
Input: A = [1, 2, 3], B = [2, 1, 3]
Output: true
Explanation:
- Push 1, Push 2
- Pop 2, Pop 1
- Push 3, Pop 3
Result: [2, 1, 3] ✓
Input: A = [1, 2, 3], B = [3, 1, 2]
Output: false
Explanation: Cannot achieve this order using stack operations
Approach 1: Brute Force (Generate All Permutations)
Intuition
Generate all possible stack permutations of array A and check if array B matches any of them. This involves exploring all possible sequences of push and pop operations.
Algorithm
- Use recursion to simulate all possible push/pop sequences
- At each step, either:
- Push next element from input (if available)
- Pop from stack (if stack is not empty)
- When input is exhausted and stack is empty, check if result matches B
- Use backtracking to explore all possibilities
java
import java.util.*;
public class StackPermutation {
public static boolean generatePermutations(int[] A, int[] B,
int inputIdx, Stack<Integer> stk,
List<Integer> result) {
// Base case: all elements processed
if (inputIdx == A.length && stk.isEmpty()) {
if (result.size() != B.length) return false;
for (int i = 0; i < B.length; i++) {
if (!result.get(i).equals(B[i])) return false;
}
return true;
}
// Option 1: Push next element from input
if (inputIdx < A.length) {
stk.push(A[inputIdx]);
if (generatePermutations(A, B, inputIdx + 1, stk, result)) {
return true;
}
stk.pop();
}
// Option 2: Pop from stack
if (!stk.isEmpty()) {
int top = stk.pop();
result.add(top);
if (generatePermutations(A, B, inputIdx, stk, result)) {
return true;
}
result.remove(result.size() - 1);
stk.push(top);
}
return false;
}
public static boolean isStackPermutationBruteForce(int[] A, int[] B) {
if (A.length != B.length) return false;
return generatePermutations(A, B, 0, new Stack<>(), new ArrayList<>());
}
public static void main(String[] args) {
int[] A = {1, 2, 3};
int[] B = {2, 1, 3};
System.out.println(isStackPermutationBruteForce(A, B)); // true
}
}Complexity Analysis
- Time Complexity: O(n!) - exploring all possible permutations
- Space Complexity: O(n) - recursion stack and temporary storage
Approach 2: Optimal (Simulation with Stack)
Intuition
Instead of generating all permutations, we simulate the process directly. We iterate through array B (the target output). For each element in B, we push elements from A onto the stack until we find the required element, then pop it. If at any point the stack top doesn't match and we've exhausted A, it's not a valid stack permutation.
Algorithm
- Initialize a stack and pointer to current position in A
- For each element in B:
- Push elements from A onto stack until stack top equals current B element
- If stack top matches, pop and move to next B element
- If we've exhausted A and stack top doesn't match, return false
- Return true if all elements of B are processed
java
import java.util.*;
public class StackPermutation {
public static boolean isStackPermutation(int[] A, int[] B) {
if (A.length != B.length) return false;
int n = A.length;
Stack<Integer> stk = new Stack<>();
int j = 0; // Pointer for array A
for (int i = 0; i < n; i++) {
// Push elements from A until we find B[i]
while (j < n && (stk.isEmpty() || stk.peek() != B[i])) {
stk.push(A[j]);
j++;
}
// Check if top matches current element of B
if (stk.peek() != B[i]) {
return false;
}
// Pop the matching element
stk.pop();
}
return true;
}
public static void main(String[] args) {
System.out.println("Test 1: " + isStackPermutation(
new int[]{1, 2, 3}, new int[]{2, 1, 3})); // true
System.out.println("Test 2: " + isStackPermutation(
new int[]{1, 2, 3}, new int[]{3, 1, 2})); // false
System.out.println("Test 3: " + isStackPermutation(
new int[]{1, 2, 3}, new int[]{1, 2, 3})); // true
System.out.println("Test 4: " + isStackPermutation(
new int[]{1, 2, 3}, new int[]{3, 2, 1})); // true
}
}Complexity Analysis
- Time Complexity: O(n) - each element is pushed and popped at most once
- Space Complexity: O(n) - stack can hold up to n elements
Approach 3: Alternative Optimal (Queue-based Simulation)
Intuition
Use a queue to represent the input sequence A. For each element in B, either pop from stack if it matches, or transfer elements from queue to stack until we find the match.
Algorithm
- Put all elements of A in a queue
- For each element in B:
- If stack top matches, pop from stack
- Else, transfer elements from queue to stack until match found or queue empty
- If no match found, return false
- Return true if B is completely processed
java
import java.util.*;
public class StackPermutation {
public static boolean isStackPermutationQueue(int[] A, int[] B) {
if (A.length != B.length) return false;
int n = A.length;
Queue<Integer> q = new LinkedList<>();
Stack<Integer> stk = new Stack<>();
// Put all elements of A in queue
for (int x : A) {
q.offer(x);
}
for (int i = 0; i < n; i++) {
int target = B[i];
// If stack top matches, pop it
if (!stk.isEmpty() && stk.peek() == target) {
stk.pop();
continue;
}
// Transfer from queue to stack until we find target
boolean found = false;
while (!q.isEmpty()) {
int front = q.poll();
if (front == target) {
found = true;
break;
}
stk.push(front);
}
if (!found) return false;
}
return stk.isEmpty() && q.isEmpty();
}
public static void main(String[] args) {
System.out.println("Test 1: " + isStackPermutationQueue(
new int[]{1, 2, 3}, new int[]{2, 1, 3})); // true
System.out.println("Test 2: " + isStackPermutationQueue(
new int[]{1, 2, 3}, new int[]{3, 1, 2})); // false
}
}Complexity Analysis
- Time Complexity: O(n) - each element is processed once
- Space Complexity: O(n) - queue and stack combined hold n elements
Key Takeaways
- Stack Permutation: Not all permutations of an array are stack permutations
- Valid Pattern: [3, 1, 2] is invalid because 1 cannot come before 2 after 3 is popped
- Catalan Number: The number of valid stack permutations of n elements is the nth Catalan number
- Simulation Approach: Simulate actual stack operations rather than generating all permutations
- Real-world Application: Used in compiler design, train car rearrangement problems
- This problem tests understanding of how stack operations affect element ordering