Solution Approach
The solution approach is quite simple. You might have gotten the idea a bit. Since we need to shift all the other elements to the left by one and also push the front element if after decrementing it is greater than 1, we get an intuition that a queue should be used. So, while doing the operations, we will do it on a queue rather than an array.
Steps are:
- Input the number of elements in the Queue, n, and the value of k.
- Input the n numbers in an array.
- Push the elements in a queue of pairs, q, along with their indexes.
-
Run a loop for k times. In each iteration of this for loop,
- Check if the Queue is empty. If yes, break out of the loop.
- Pop-out the front element of the Queue. Decrement the first element of the front element by 1. If the value is still greater than 0, push this pair back in the Queue. Else, continue to the next iteration.
- After the loop ends, either the Queue will be empty, there will be some elements in it. If the Queue is empty, print (“Array becomes empty”). Otherwise, print the second elements of each element of the Queue.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n; // Input the number of elements in the array
int a[n]; // Declare the array for storing the n numbers
int k;
cin>>k; // Input the value of k
queue<pair<int,int>>q; // Declare the queue of pairs
for(int i=0;i<n;i++){
cin>>a[i]; // Input the numbers of the array one by one
q.push({a[i],i}); // Push the numbers along with their indices into the //queue.
}
for(int i=0;i<k;i++){
// for each of the k operations
if(q.empty()){ // Check if the queue is empty. If yes, break out of the //loop as we can't do any more operations
break;
}
else{
pair<int,int> x = q.front(); // Store the front element of the queue //and pop it out.
q.pop();
int u = x.first;
u--; // Decrement the first element of the front as it is the number
if(u>0){ // If after decrementing, the value is greater than 0, push //the pair at the back of the queue.
q.push({u,x.second});
}
}
}
if(q.empty()){ // If the queue becomes empty, print ARRAY BECOMES EMPTY
cout<<"ARRAY BECOMES EMPTY"<<endl;
}
else{
while(!q.empty()){ // Else, print out the indices one by one by printing //the second element of the queue front
cout<<q.front().second<<" ";
q.pop();
}
cout<<endl;
}
}
You can also try this code with Online C++ Compiler
Run Code
Input
6 //n
2,5,6,8,10,11 //a
2 //k
You can also try this code with Online C++ Compiler
Run Code
Output
2 3 4 5 0 1
You can also try this code with Online C++ Compiler
Run Code
Complexities
Time complexity
O(max(n,k)), where k= number of operations to be performed and n = the number of elements in the array.
Reason: We use one loop of length k whose time complexity will be O(k). And in the end, we have one loop to print the indexes which is of length equal to the number of elements present in the queue. Since, in the worst case, the maximum number of elements present in the queue can be equal to n, so the time complexity of printing the indexes is O(n).
Hence, the total time complexity is equal to O(k)+O(n) which is approximately O(max(n,k)).
Space complexity
The Space Complexity is O(n), where n = the number of elements in the array.
Reason: we’re storing the numbers in the array and the Queue. Both take O(n) space.
Read about Application of Queue in Data Structure here.
Frequently Asked Questions
What are queues in data structure?
A queue is a linear data structure that follows the FIFO (first in, first out) property.
What are the different types of queues in data structure?
There are four types of queues – simple/linear Queue, Circular Queue, priority queue, and double-ended Queue.
Write the different applications of queue data structure.
Queues are applied in places where data has to be stored but not processed immediately. Some examples include – CPU scheduling, printer queue, phone calling system, etc.
Why do we need an array?
Elements in an array can be accessed very easily. They are best to use when we need to store multiple values of the same type.
How to get the front element of a queue?
We use the in-built function q.front() to get the front element of the Queue.
Check out this problem - First And Last Occurrences Of X
Conclusion
In this article, we discussed the problem of finding the index of the array elements after performing given operations k times. A major takeaway from this problem is the implementation of the idea using a queue data structure. This problem tells you how to use the queue functions efficiently. Some more problems based on the queue data structure are: reversing a queue, reversing the first k elements of a queue, and implementing of Queue.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Coding!