Rearrange and update array elements as specified by the given queries
Last Updated : 24 Feb, 2023
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 operations void 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 Code int 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 program to implement // the above approach import java.util.*; class GFG{ // Function to perform the // given operations static 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 Code public 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 program to implement # the above approach from collections import deque # Function to perform the # given operations def 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 Code if __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
<script> // Javascript program to implement // the above approach // Function to perform the // given operations function 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 Code let arr=[1, 2, 3, 4, 5]; let N = arr.length; // Vector<Vector<Integer> // > Q = new Vector<>(); // All possible Queries let Q = [[0], [1], [3, 1], [2, 2, 54], [3, 2]]; Queries(arr, N, Q); // This code is contributed by unknown2108 </script> using System; public class Program { // Function to perform the given operations public static void Queries(int[] arr, int N, int[][] Q) { // Dequeue to store the array elements int[] 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 Code public 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); } } Time Complexity: O(N+|Q|)
Auxiliary Space: O(N)
Similar Reads
Queries to update array elements in a range [L, R] to satisfy given conditions Given an array arr[] consisting of N 0s and an array Q[][] with each row of the form (L, R)., the task for each query is to update all the array elements in the range [L, R] such that arr[i] = i - L + 1. Examples: Input: arr[] = { 0, 0, 0, 0 }, Q[][] = { { 1, 2 }, { 0, 1 } } Output: 1 3 2 0 Explanat
9 min read
Queries to update array by adding or multiplying array elements and print the element present at specified index Given an array arr[] consisting of N integers and an array Q[] of M pairs representing a query of type {X, Y}, the task is to perform queries of the following type: Query(0, X): Add integer X to every array elements.Query(1, Y): Multiply each array element by Y.Query(2, i): Print the value at index
9 min read
Queries to replace every array element by its XOR with a given value with updates Given an array, initially consisting of 0 as the only element present and Q operations of the following two types: Add(X): Insert X into the array.Update(X): Replace every array element Ai by Ai ^ X, where ^ is the XOR operation. Examples: Input: Q = 2Add(5)Update(2)Output: 2 7Explanation:Initially,
5 min read
Queries to update Subarrays of a given Array using Disjoint Set Given an array arr[] consisting of N integers, consisting only of 0's initially and queries Q[][] of the form {L, R, C}, the task for each query is to update the subarray [L, R] with value C. Print the final array generated after performing all the queries. Examples: Input: N = 5, Q = {{1, 4, 1}, {3
10 min read
Binary Indexed Tree : Range Updates and Point Queries Given an array arr[0..n-1]. The following operations need to be performed. update(l, r, val): Add ‘val’ to all the elements in the array from [l, r].getElement(i): Find element in the array indexed at ‘i’. Initially all the elements in the array are 0. Queries can be in any order, i.e., there can be
15+ min read
Find the final Array by updating given Ranges Given an array arr[] consisting of N integers and an array Q[][3] consisting of M queries of the form [L, R, U], the task for each query is to xor every array element over the range [L, R] with U, After processing each query print the final array. Examples: Input: arr[] = {0, 0, 0, 0, 0, 0, 0}, Q[][
10 min read