879170. Reverse First K of Queue
Reverse First K of Queue
Slug: reverse-first-k-elements-of-queue--123903
Difficulty: Easy
Id: 879170
Topic Tags: Stack, Queue, Data Structures
Company Tags: Amazon
Summary
The problem is to reverse the first k elements in a queue. The input will be an integer k and a queue of integers. You need to modify the queue such that the first k elements are reversed.
This problem involves basic concepts of queues and data structures. It requires you to implement a solution using a stack or another queue.
Detailed Explanation
To solve this problem, we can use two queues. The idea is to dequeue all elements from the original queue and enqueue them into a new queue until we have dequeued k elements. Then, we start dequeuing elements from the new queue and enqueueing them back into the original queue until there are no more elements left in the new queue.
Here's a step-by-step breakdown of the solution:
- Initialize an empty queue (newQueue) to store the reversed elements.
- Dequeue all elements from the original queue and enqueue them into the newQueue.
- Dequeue k elements from the newQueue and enqueue them back into the original queue.
- Repeat step 3 until there are no more elements left in the newQueue.
- Return the modified original queue.
Time complexity: O(n + k), where n is the number of elements in the original queue. The first loop (steps 1-2) takes O(n) time, and the second loop (step 3) takes O(k) time. Since we repeat step 3 until there are no more elements left in the newQueue, which happens after k iterations, the total time complexity is O(n + k).
Space complexity: O(n), where n is the number of elements in the original queue. We create a new queue to store the reversed elements, and its size can be as large as the input queue.
Optimized Solutions
Java
import java.util.LinkedList;
import java.util.Queue;
public class ReverseFirstKQueue {
public static void reverseFirstK(Queue<Integer> queue, int k) {
Queue<Integer> newQueue = new LinkedList<>();
for (int i = 0; i < k; i++) {
newQueue.add(queue.poll());
}
while (!newQueue.isEmpty()) {
queue.add(newQueue.poll());
}
}
}