Interleave the first half of a queue with the second half

Medium

Problem

Given a queue of even length, interleave its first half with its second half: first[0], second[0], first[1], second[1], …

Example 1

Input:  [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Output: [11, 16, 12, 17, 13, 18, 14, 19, 15, 20]

Also asked as: Interleave the first half of the queue with second half

Test cases

Case 1

Input:    [11,12,13,14,15,16,17,18,19,20]
Expected: [11,16,12,17,13,18,14,19,15,20]

Case 2

Input:    [1,2,3,4]
Expected: [1,3,2,4]

Case 3

Input:    [1,2]
Expected: [1,2]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Move first half to a stack, re-queue, then interleave

Time O(n)Space O(n)

Push the first n/2 to a stack, enqueue back (now the front half is reversed and rotated), rotate n/2, then alternately pull from stack-equivalent and queue.

function interleaveQueue(q) {
const half = q.length / 2;
const st = [];
for (let i = 0; i < half; i++) st.push(q.shift());
while (st.length) q.push(st.pop());
for (let i = 0; i < half; i++) q.push(q.shift());
for (let i = 0; i < half; i++) { st.push(q.shift()); }
const res = [];
for (let i = 0; i < half; i++) { res.push(st.pop()); res.push(q.shift()); }
q.push(...res);
return q;
}