Log inSign up
easyGeeksforGeeksNot Started

Reverse First K Elements of Queue

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer K and a queue of integers, we need to reverse the order of the first K elements of the queue, leaving the other elements in the same relative order.

Only following standard operations are allowed on queue: - enqueue(x) : Add an item x to rear of queue - dequeue() : Remove an item from front of queue - size() : Returns number of elements in queue. - front() : Finds front item.

If K is larger than the size of the queue or K <= 0, the queue remains unchanged.

Example 1 · Reverse First 3 Elements:

Input: Q = [1, 2, 3, 4, 5], K = 3
Output: [3, 2, 1, 4, 5]
Explanation: After reversing the first 3 elements, the queue becomes [3, 2, 1, 4, 5].

Example 2 · Reverse First 4 Elements:

Input: Q = [10, 20, 30, 40, 50], K = 4
Output: [40, 30, 20, 10, 50]
Explanation: After reversing the first 4 elements, the queue becomes [40, 30, 20, 10, 50].

Constraints:

  • 1 <= K <= N <= 105
  • 1 <= elements of Queue <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue Reversal
  • Queue FIFO Mechanics

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Combine stack inversion with cyclic queue rotation.
  • Manipulate queue ordering in-place using restricted FIFO primitives.
  • Avoid unnecessary O(N) auxiliary allocations when O(K) suffices.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partial sequence reversal on FIFO collections.
  • Maintaining relative order of suffix elements while inverting prefix.

Algorithmic Decision Tree:

  • Step 1: Move K elements from Queue -> Stack.
  • Step 2: Move K elements from Stack -> Queue.
  • Step 3: Rotate (N - K) elements: q.push(q.pop()).

Connected Patterns:

Queue ReversalImplement Queue using StacksRotate Array

1. Brute Force — Full Array Extraction & Slice Reversal

Intuition

Drain queue into an array, reverse the first K indices, and rebuild queue.

Algorithm

  1. Step 1: Drain queue into array arr.
  2. Step 2: Reverse arr[0...K-1] using two pointers.
  3. Step 3: Enqueue all elements of arr back into q.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <vector>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 queue<int> modifyQueue(queue<int> q, int k) {
11 vector<int> arr;
12 while (!q.empty()) {
13 arr.push_back(q.front());
14 q.pop();
15 }
16 reverse(arr.begin(), arr.begin() + k);
17 for (int x : arr) {
18 q.push(x);
19 }
20 return q;
21 }
22};
23
24int main() {
25 Solution sol;
26 queue<int> q;
27 for (int i = 1; i <= 5; ++i) q.push(i);
28 queue<int> res = sol.modifyQueue(q, 3);
29 while (!res.empty()) {
30 cout << res.front() << " ";
31 res.pop();
32 }
33 cout << endl; // 3 2 1 4 5
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — Dumping N elements to list and reversing prefix of size K takes O(N).
  • Space complexity: O(N) — Allocates array of size N.

Why Brute Force Doesn't Scale:

Copying 105 elements between arrays causes unnecessary GC pressure.

Stack of size K with in-place rotation completes in under 3ms.

2. Better — Separate Stack and Queue Buffer

Intuition

Place the first K elements in a stack and the remaining elements in a helper queue, then combine.

Algorithm

  1. Step 1: Pop K elements from q and push to stack st.
  2. Step 2: Pop remaining elements from q into helper queue helper.
  3. Step 3: Pop all elements from st back into q.
  4. Step 4: Pop all elements from helper back into q.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <stack>
4
5using namespace std;
6
7class Solution {
8public:
9 queue<int> modifyQueue(queue<int> q, int k) {
10 stack<int> st;
11 queue<int> helper;
12
13 for (int i = 0; i < k; ++i) {
14 st.push(q.front());
15 q.pop();
16 }
17 while (!q.empty()) {
18 helper.push(q.front());
19 q.pop();
20 }
21 while (!st.empty()) {
22 q.push(st.top());
23 st.pop();
24 }
25 while (!helper.empty()) {
26 q.push(helper.front());
27 helper.pop();
28 }
29 return q;
30 }
31};
32
33int main() {
34 Solution sol;
35 queue<int> q;
36 for (int i = 1; i <= 5; ++i) q.push(i);
37 queue<int> res = sol.modifyQueue(q, 3);
38 while (!res.empty()) {
39 cout << res.front() << " ";
40 res.pop();
41 }
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Splits N elements into stack of size K and queue of size N-K.
  • Space complexity: O(N) — Allocates auxiliary stack and auxiliary queue.

3. Optimal — In-Place Rotation with Size-K Stack

Intuition

Push first K elements to stack and pop back to queue. Now the queue has un-reversed elements at front and reversed elements at back. Rotate the first N-K elements to the back!

Algorithm

  1. Step 1: If q.empty() or k <= 0 or k > q.size(), return q.
  2. Step 2: Push first k elements of q into a stack st.
  3. Step 3: Pop all elements from st and enqueue them back into q (they land at rear).
  4. Step 4: Rotate the remaining q.size() - k elements by popping from front and pushing to back.
  5. Step 5: Return q.

Stack Inversion + Queue Rotation Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Queue: [4, 5]
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
4
5
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
Move K=3 items to Stack
Why this step matters

Queue: [4, 5]. Stack: [1, 2, 3] (top is 3).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3#include <stack>
4
5using namespace std;
6
7class Solution {
8public:
9 queue<int> modifyQueue(queue<int> q, int k) {
10 if (q.empty() || k <= 0 || k > q.size()) return q;
11
12 stack<int> st;
13 int n = q.size();
14
15 // 1. Push first k elements into stack
16 for (int i = 0; i < k; ++i) {
17 st.push(q.front());
18 q.pop();
19 }
20
21 // 2. Enqueue back reversed elements
22 while (!st.empty()) {
23 q.push(st.top());
24 st.pop();
25 }
26
27 // 3. Move remaining (n - k) elements to the back
28 for (int i = 0; i < n - k; ++i) {
29 q.push(q.front());
30 q.pop();
31 }
32
33 return q;
34 }
35};
36
37int main() {
38 Solution sol;
39 queue<int> q;
40 q.push(1); q.push(2); q.push(3); q.push(4); q.push(5);
41 queue<int> res = sol.modifyQueue(q, 3);
42 while (!res.empty()) {
43 cout << res.front() << " ";
44 res.pop();
45 }
46 cout << endl; // 3 2 1 4 5
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N) — K pushes/pops to stack + (N - K) rotations in queue = O(N) linear time.
  • Space complexity: O(K) Auxiliary Stack — Stack holds at most K elements.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Full Array ConversionO(N)O(N)Convert queue to array, reverse the first K elements with two pointers, and reload queue.Array conversion.
2.Better — Auxiliary Queue + StackO(N)O(N)Put first K elements in Stack, put remaining N-K elements in a second Queue. Reassemble.Dual structure memory allocation.
3.Optimal — Stack Inversion + In-Place Queue RotationOptimalO(N)O(K)Use a Stack of size K for prefix inversion. Rotate the suffix (N - K) elements in-place using queue self-rotation.None. Exactly 2K + (N - K) operations.

Common Pitfalls & Crucial Edge Cases

Forgetting the (N - K) rotation step

Leaving the reversed elements at the rear produces [4, 5, 3, 2, 1] instead of [3, 2, 1, 4, 5].

Calculating `n - k` inside loop

Store n = q.size() before modifying the queue to avoid altering the iteration count dynamically.

Crucial Edge Cases to Validate:

  • K == N — Entire queue is reversed (equivalent to full Queue Reversal).
  • K == 1 — Queue remains identical since reversing a single element is a no-op.
  • K > N or K <= 0 — Returns original queue unchanged.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the 3-step algorithm out loud before coding: '1) Stack push K, 2) Queue push K from stack, 3) Rotate N-K elements.'
  2. Emphasize the O(K) space advantage over O(N) full queue copying.
  3. Trace through a simple example with k=2 and n=4 to confirm the final rotation count (n - k).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we rotate the remaining (N - K) elements to the back of the queue?

2.What is the auxiliary space complexity of the optimal solution?

3.What is the outcome if K = 1?

Back to DSA Sheet