Reverse the first K elements of a queue

The problem, simply

You get a queue, a waiting line, and a number k. Reverse the order of the first k items. The other items must stay behind them, in the same order as before.

You may only use queue moves: take from the front, add at the back, look at the front, and ask for the size. You may also use a stack.

A story to remember it

Picture it

Examples

Way 1: the simple way

Copy everything out into a list, flip the first k boxes of the list, and copy it all back.

1. Move all n items from the queue into a list.
2. Reverse the first k positions of the list.
3. Add every item of the list back into the queue.

import java.util.*;

class Solution {
    public void reverseFirstK(Queue<Integer> q, int k) {
        if (k < 0 || k > q.size()) return;
        List<Integer> all = new ArrayList<>();
        while (!q.isEmpty()) all.add(q.poll());          // pour everything out
        Collections.reverse(all.subList(0, k));          // flip the first k
        for (int x : all) q.offer(x);                    // pour it back
    }
}

How long it takes: every item moves out and back once, O(n). Extra room: the list holds all n items, O(n).

Way 2: the clever way

Only the first k items need a helper. A stack reverses them, and a rotation puts the rest behind them.

1. Take k items from the front and push them on a stack.
2. Pop them all and add each to the back of the queue. They are now at the back, reversed.
3. Move the other n - k items from the front to the back, one by one.

import java.util.*;

class Solution {
    public void reverseFirstK(Queue<Integer> q, int k) {
        int n = q.size();
        if (k < 0 || k > n) return;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < k; i++) stack.push(q.poll());     // 1. first k up the ladder
        while (!stack.isEmpty()) q.offer(stack.pop());       // 2. down again, reversed, to the back
        for (int i = 0; i < n - k; i++) q.offer(q.poll());   // 3. the rest walk around behind them
    }
}

How long it takes: k pushes, k pops, and n - k rotations, O(n). Extra room: the stack holds only k items, O(k).

Another way: recursion instead of the stack

The call stack can play the ladder. Hold the front item, reverse the next k - 1 items with a recursive call, then add the held item at the back. After that, rotate the other n - k items.

import java.util.*;

class Solution {
    public void reverseFirstK(Queue<Integer> q, int k) {
        int n = q.size();
        if (k < 0 || k > n) return;
        sendReversed(q, k);                                   // the first k go to the back, reversed
        for (int i = 0; i < n - k; i++) q.offer(q.poll());
    }

    private void sendReversed(Queue<Integer> q, int k) {
        if (k == 0) return;
        int front = q.poll();             // hold this one
        sendReversed(q, k - 1);           // the next k - 1 go to the back first, reversed
        q.offer(front);                   // then this one, so it lands after them
    }
}

Same O(n) time and O(k) room, but the room is the call stack, so a huge k can overflow it.

Watch out for

• Rotating n or k times instead of n - k. Save n = q.size() before you change the queue, then rotate exactly n - k times.
• Not checking k. A k bigger than the queue makes poll() return null, which crashes when unboxed. A negative k makes no sense.
• Reading q.size() inside the rotation loop. It does not change during a rotation here, but saving n first avoids confusion.

What interviewers ask next

• Reverse the whole queue: that is k = n, and step 3 does nothing.
• Reverse the queue in groups of k: repeat steps 1 and 2 for every full group. Each group goes to the back in turn, so the groups keep their order. Rotate any leftover items at the end.
• Reverse only the last k items: rotate the first n - k items to the back first, then reverse the next k with the stack.
• Can you do it with no stack and no recursion? Not with plain queue moves, because a rotation never changes the circular order of the items.

Remember this

Grown-up words: the waiting line is a queue, the ladder is a stack, walking from front to back is a rotation, and the recursion version uses the call stack as the helper.