Given an array arr[] of size N and queries Q[][], the task is to perform the following types of queries on the given array. 0: Left shift the array by one position.
- 1: Right shift the array by one position.
- 2 X Y: Update the value of arr[X] = Y.
- 3 X: Print arr[X].
Example:
Input: arr[]={1, 2, 3, 4, 5}, Q[][]={{0}, {1}, {3, 1}, {2, 2, 54}, {3, 2}}.
Output:4 54
Explanation:
Query1: The array arr[] modifies to {2, 3, 4, 5, 1}
Query2: The array arr[] modifies to {1, 2, 3, 4, 5}
Query3: Print the value of arr[1] i.e. 2
Query4: The array arr[] modifies to {1, 54, 3, 4, 5}
Query5: Print the value of arr[2], i.e. 54.Input: arr[]={1}, Q[][]={{0}, {1}, {2, 0, 54}, {3, 0}}
Output: 54
Approach: The problem can be solved using Deque(Double Ended queue) to perform the insert and delete operation at the front and back of the queue in O(1). Follow the below steps to solve the problem.
- Create a double-ended Queue, dq.
- Push all elements of the array arr[] to dq.
- For the query of type 0(Left Shift), pop an element from the front of dq and push the element to the back of dq.
- For the query of type 1(Right Shift), pop an element from the back of dq and push the element to the front of dq.
- For the query of type 2, update dq[X] = Y.
- For the query of type 3, print dq[X].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the// given operationsvoid Queries(int arr[], int N, vector<vector<int> >& Q){ // Dequeue to store the // array elements deque<int> dq; // Insert all element of // the array into the dequeue for (int i = 0; i < N; i++) { dq.push_back(arr[i]); } // Stores the size of the queue int sz = Q.size(); // Traverse each query for (int i = 0; i < sz; i++) { // Query for left shift. if (Q[i][0] == 0) { // Extract the element at // the front of the queue int front = dq[0]; // Pop the element at // the front of the queue dq.pop_front(); // Push the element at // the back of the queue dq.push_back(front); } // Query for right shift else if (Q[i][0] == 1) { // Extract the element at // the back of the queue int back = dq[N - 1]; // Pop the element at // the back of the queue dq.pop_back(); // Push the element at // the front of the queue dq.push_front(back); } // Query for update else if (Q[i][0] == 2) { dq[Q[i][1]] = Q[i][2]; } // Query to get the value else { cout << dq[Q[i][1]] << " "; } }}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); vector<vector<int> > Q; // All possible Queries Q = { { 0 }, { 1 }, { 3, 1 }, { 2, 2, 54 }, { 3, 2 } }; Queries(arr, N, Q); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to perform the// given operationsstatic void Queries(int arr[], int N, int [][]Q){ // Dequeue to store the // array elements Vector<Integer> dq = new Vector<>(); // Insert all element of // the array into the dequeue for (int i = 0; i < N; i++) { dq.add(arr[i]); } // Stores the size of the queue int sz = Q.length; // Traverse each query for (int i = 0; i < sz; i++) { // Query for left shift. if (Q[i][0] == 0) { // Extract the element at // the front of the queue int front = dq.get(0); // Pop the element at // the front of the queue dq.remove(0); // Push the element at // the back of the queue dq.add(front); } // Query for right shift else if (Q[i][0] == 1) { // Extract the element at // the back of the queue int back = dq.elementAt(dq.size() - 1); // Pop the element at // the back of the queue dq.remove(dq.size() - 1); // Push the element at // the front of the queue dq.add(0, back); } // Query for update else if (Q[i][0] == 2) { dq.set(Q[i][1], Q[i][2]); } // Query to get the value else { System.out.print(dq.get(Q[i][1]) + " "); } }}// Driver Codepublic static void main(String[] args){ int arr[] = {1, 2, 3, 4, 5}; int N = arr.length; // Vector<Vector<Integer> // > Q = new Vector<>(); // All possible Queries int [][]Q = {{0}, {1}, {3, 1}, {2, 2, 54}, {3, 2}}; Queries(arr, N, Q);}}// This code is contributed by Princi Singh |
Python3
# Python3 program to implement# the above approachfrom collections import deque# Function to perform the# given operationsdef Queries(arr, N, Q): # Dequeue to store the # array elements dq = deque() # Insert all element of # the array into the dequeue for i in range(N): dq.append(arr[i]) # Stores the size of the queue sz = len(Q) # Traverse each query for i in range(sz): # Query for left shift. if (Q[i][0] == 0): # Extract the element at # the front of the queue front = dq[0] # Pop the element at # the front of the queue dq.popleft() # Push the element at # the back of the queue dq.appendleft(front) # Query for right shift elif (Q[i][0] == 1): # Extract the element at # the back of the queue back = dq[N - 1] # Pop the element at # the back of the queue dq.popleft() # Push the element at # the front of the queue dq.appendleft(back) # Query for update elif (Q[i][0] == 2): dq[Q[i][1]] = Q[i][2] # Query to get the value else: print(dq[Q[i][1]], end = " ")# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 3, 4, 5 ] N = len(arr) # All possible Queries Q = [ [ 0 ], [ 1 ], [ 3, 1 ], [ 2, 2, 54 ], [ 3, 2 ] ] Queries(arr, N, Q)# This code is contributed by mohit kumar 29 |
Javascript
<script>// Javascript program to implement// the above approach// Function to perform the// given operationsfunction Queries(arr,N,Q){ // Dequeue to store the // array elements let dq = []; // Insert all element of // the array into the dequeue for (let i = 0; i < N; i++) { dq.push(arr[i]); } // Stores the size of the queue let sz = Q.length; // Traverse each query for (let i = 0; i < sz; i++) { // Query for left shift. if (Q[i][0] == 0) { // Extract the element at // the front of the queue let front = dq[0]; // Pop the element at // the front of the queue dq.shift(); // Push the element at // the back of the queue dq.push(front); } // Query for right shift else if (Q[i][0] == 1) { // Extract the element at // the back of the queue let back = dq[dq.length - 1]; // Pop the element at // the back of the queue dq.pop(); // Push the element at // the front of the queue dq.unshift( back); } // Query for update else if (Q[i][0] == 2) { dq[Q[i][1]] = Q[i][2]; } // Query to get the value else { document.write(dq[Q[i][1]] + " "); } }}// Driver Codelet arr=[1, 2, 3, 4, 5];let N = arr.length; // Vector<Vector<Integer>// > Q = new Vector<>();// All possible Querieslet Q = [[0], [1], [3, 1],[2, 2, 54], [3, 2]];Queries(arr, N, Q);// This code is contributed by unknown2108</script> |
C#
using System;public class Program{// Function to perform the given operationspublic static void Queries(int[] arr, int N, int[][] Q){// Dequeue to store the array elementsint[] dq = new int[N]; // Insert all element of the array into the dequeue for (int i = 0; i < N; i++) { dq[i] = arr[i]; } // Stores the size of the queue int sz = Q.Length; // Traverse each query for (int i = 0; i < sz; i++) { // Query for left shift. if (Q[i][0] == 0) { // Extract the element at the front of the queue int front = dq[0]; // Shift all elements one position to the left for (int j = 1; j < N; j++) { dq[j - 1] = dq[j]; } // Put the extracted element at the back of the queue dq[N - 1] = front; } // Query for right shift else if (Q[i][0] == 1) { // Extract the element at the back of the queue int back = dq[N - 1]; // Shift all elements one position to the right for (int j = N - 1; j > 0; j--) { dq[j] = dq[j - 1]; } // Put the extracted element at the front of the queue dq[0] = back; } // Query for update else if (Q[i][0] == 2) { dq[Q[i][1]] = Q[i][2]; } // Query to get the value else { Console.Write(dq[Q[i][1]] + " "); } }}// Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; // All possible Queries int[][] Q = { new int[] { 0 }, new int[] { 1 }, new int[] { 3, 1 }, new int[] { 2, 2, 54 }, new int[] { 3, 2 } }; Queries(arr, N, Q);}} |
Output:
2 54
Time Complexity: O(N+|Q|)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
