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!
