Reverse First K elements of Queue

Easy
0/40
Average time to solve is 10m
273 upvotes
Asked in companies
MicrosoftOptumAmazon

Problem statement

You are given a QUEUE containing ‘N’ integers and an integer ‘K’. You need to reverse the order of the first ‘K’ elements of the queue, leaving the other elements in the same relative order.

You can only use the standard operations of the QUEUE STL:

1. enqueue(x) : Adds an item x to rear of the queue
2. dequeue() : Removes an item from front of the queue
3. size() : Returns number of elements in the queue.
4. front() : Finds the front element.
For Example: 
Let the given queue be { 1, 2, 3, 4, 5 } and K be 3.
You need to reverse the first K integers of Queue which are 1, 2, and 3.
Thus, the final response will be { 3, 2, 1, 4, 5 }.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of queries or test cases. 

The first line of each input consists of 2 space-separated integers ‘N’ and ‘K’ denoting the size of the queue and the number of elements to be reversed from the front.

The second line of each input consists of ‘N’ space-separated integers denoting the elements of the queue.
Output format: 
For each test case, print the elements of the queue after reversing the order of first ‘K’ elements in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up 
Can you solve this without using arrays?
Constraints: 
1 <= T <= 10
1 <= N <= 10 ^ 5
0 <= K <= N
-10 ^ 9 <= queue elements <= 10 ^ 9

  Time limit: 1 sec
Sample Input 1:
2
5 3
1 2 3 4 5
4 2
6 2 4 1
Sample Output 1:
3 2 1 4 5
2 6 4 1
Explanation:
For test case 1: Refer to the example explained above.

For test case 2:
The queue after reversing the first 2 elements i.e., 6 and 2 will be { 2, 6, 4, 1 }.
Sample Input 2:
2
5 2
5 3 2 6 4
4 4
1 2 3 4
Sample Output 2:
3 5 2 6 4
4 3 2 1
Hint

We can use an array to reverse the elements.

Approaches (2)
Array

The very first approach can be to use an array to reverse the elements.

What needs to be done is: 

  • Store all the elements of the queue in an array.
  • Reverse first K elements of the array.
  • Push all elements of the array into the queue.
     

The algorithm is as follows:

  • Initialize N = Queue.size
  • Create an array ARR of size equal to the size of the queue.
  • Loop for( i = 0 to N ):
    • ARR[ i ] = Queue.front()
    • Q.pop()
  • reverse(ARR, ARR + K)
  • Loop for( i = 0 to N )
    • Queue.push( ARR[ i ] )
  • Return Queue.
Time Complexity

O(N), where N is the size of the queue.

 

In the worst case, we are pushing and popping all the elements of the queue that takes O(N) time. Hence, the overall Time Complexity is O(N).

Space Complexity

O(N), where N is the size of the queue.

 

In the worst case, we are creating an array of size N. Hence, the overall Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Reverse First K elements of Queue
Full screen
Console