Stacks & QueuesProblem 29 of 38
Interleave the first half of the queue with second half
Problem Statement
Given a queue of even length, interleave the first half with the second half. The first element of the first half should be followed by the first element of the second half, and so on.
Example:
Input: Queue = [1, 2, 3, 4, 5, 6, 7, 8]
First half: [1, 2, 3, 4]
Second half: [5, 6, 7, 8]
Output: Queue = [1, 5, 2, 6, 3, 7, 4, 8]
Interleaving: 1, 5, 2, 6, 3, 7, 4, 8
Approach 1: Brute Force (Using Extra Queue)
Intuition
Use two auxiliary data structures: one to hold the first half and another for the second half. Then interleave them by alternately taking elements from each half.
Algorithm
- Dequeue first half elements into a separate container
- Dequeue second half elements into another container
- Alternately enqueue from first and second containers
- This reconstructs the interleaved queue
java
import java.util.*;
public class InterleaveQueue {
public static void interleaveBruteForce(Queue<Integer> q) {
int n = q.size();
if (n % 2 != 0) return; // Must be even
List<Integer> firstHalf = new ArrayList<>();
List<Integer> secondHalf = new ArrayList<>();
int half = n / 2;
// Store first half
for (int i = 0; i < half; i++) {
firstHalf.add(q.poll());
}
// Store second half
for (int i = 0; i < half; i++) {
secondHalf.add(q.poll());
}
// Interleave
for (int i = 0; i < half; i++) {
q.offer(firstHalf.get(i));
q.offer(secondHalf.get(i));
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 8; i++) q.offer(i);
System.out.println("Original queue: " + q);
interleaveBruteForce(q);
System.out.println("Interleaved queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - each element processed once
- Space Complexity: O(n) - storing both halves
Approach 2: Optimal (Using Stack and Queue)
Intuition
Use a stack to reverse the first half, then use the queue itself for interleaving. This reduces space usage to O(n/2).
Algorithm
- Dequeue first half elements into a stack
- Pop all from stack and enqueue (reverses first half)
- Dequeue half elements and enqueue (first half now at end)
- Dequeue first half to stack again
- Interleave by alternating stack pop and queue dequeue
java
import java.util.*;
public class InterleaveQueue {
public static void interleaveQueue(Queue<Integer> q) {
int n = q.size();
if (n % 2 != 0) return;
Stack<Integer> stk = new Stack<>();
int half = n / 2;
// Step 1: Push first half to stack
for (int i = 0; i < half; i++) {
stk.push(q.poll());
}
// Step 2: Pop from stack and enqueue (reverses first half)
while (!stk.isEmpty()) {
q.offer(stk.pop());
}
// Step 3: Move first half (now second half) to end
for (int i = 0; i < half; i++) {
q.offer(q.poll());
}
// Step 4: Push first half to stack again
for (int i = 0; i < half; i++) {
stk.push(q.poll());
}
// Step 5: Interleave - alternate stack pop and queue dequeue
while (!stk.isEmpty()) {
q.offer(stk.pop());
q.offer(q.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 8; i++) q.offer(i);
System.out.println("Original queue: " + q);
interleaveQueue(q);
System.out.println("Interleaved queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - multiple passes but each O(n)
- Space Complexity: O(n/2) - stack holds half the elements
Approach 3: Simplified Using Stack (First Half Only)
Intuition
A simpler approach: just store the first half in a stack, then interleave by popping from stack and dequeuing from queue.
Algorithm
- Store first half in stack
- Interleave: pop from stack, dequeue from queue (second half)
- This gives interleaved result
java
import java.util.*;
public class InterleaveQueue {
public static void interleaveSimple(Queue<Integer> q) {
int n = q.size();
if (n % 2 != 0) return;
int half = n / 2;
Queue<Integer> firstHalf = new LinkedList<>();
// Store first half in auxiliary queue
for (int i = 0; i < half; i++) {
firstHalf.offer(q.poll());
}
// Interleave: alternate between firstHalf and q (which has second half)
while (!firstHalf.isEmpty()) {
q.offer(firstHalf.poll());
q.offer(q.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= 8; i++) q.offer(i);
System.out.println("Original queue: " + q);
interleaveSimple(q);
System.out.println("Interleaved queue: " + q);
}
}Complexity Analysis
- Time Complexity: O(n) - each element processed once
- Space Complexity: O(n/2) - storing first half
Visual Walkthrough
Original: [1, 2, 3, 4, 5, 6, 7, 8]
|--first--|--second--|
Step 1: Extract first half to auxiliary
FirstHalf: [1, 2, 3, 4]
Queue: [5, 6, 7, 8]
Step 2: Interleave
Iteration 1: enqueue 1, enqueue 5 → Queue: [6, 7, 8, 1, 5]
Iteration 2: enqueue 2, enqueue 6 → Queue: [7, 8, 1, 5, 2, 6]
Iteration 3: enqueue 3, enqueue 7 → Queue: [8, 1, 5, 2, 6, 3, 7]
Iteration 4: enqueue 4, enqueue 8 → Queue: [1, 5, 2, 6, 3, 7, 4, 8]
Result: [1, 5, 2, 6, 3, 7, 4, 8]
Key Takeaways
- Even Length Required: Queue must have even number of elements
- Two Halves: Split queue into two equal halves
- Auxiliary Space: Need O(n/2) extra space for one half
- Alternating Pattern: Take one from each half alternately
- Self-Modifying Queue: Second half can stay in queue while interleaving
- This pattern is useful in shuffle algorithms and parallel processing