Reorder and update array elements according to a given query

In this question we will execute the given query on the array elements. The query contains a loop of left rotation, right rotation, and update of array elements.

The logical part of solving the problem is array rotation. A simple way to rotate an array to the left is to replace each element with the next element and the last element with the first element.

We can use the deque data structure to rotate the array efficiently.

Problem Statement - We are given an arr[] array containing integer values. Additionally, we are given a requests[] array containing K queries. We need to execute each query given in requests[] on arr[] array elements according to the following rules.

• {0} - Performs a circular left rotation on an array.

• {1) - Perform a circular right rotation on the array.

• {2, p, q} - Updates the element at index p with q.

• {3, p} - Prints the element at index p.

Example

enter

arr[] = {8, 9, 13, 44, 76, 67, 21, 51}; queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};

Output

13,223

Explanation- Let’s execute each query.

• {1} -> After rotating the array to the right, the array becomes {51, 8, 9, 13, 44, 76, 67, 21}

• {0} -> After rotating the updated array to the left, the array becomes equal to {8, 9, 13, 44, 76, 67, 21, 51}.

• {2, 4, 50} -> After updating the element at index 4 to 50, the array becomes {8, 9, 13, 44, 50, 67, 21, 51}

• {3, 2} -> It prints the element at the second index.

• {2, 2, 223}−> Update the element at the second index to 223, and the array becomes {8, 9, 223, 44, 50, 67, 21, 51}. p>

• {3, 2} -> It prints the element at the second index.

enter

arr[] = {3, 2, 1}, {{3, 2}, {3, 0}}

Output

1,3

Description - It prints the array from 2nd and 0th index.

enter

arr[] = {76,20,51,78}, queries={{1},{1},{3, 1}}

Output

78

Explanation- After rotating the array to the right 2 times, the array becomes [51, 78, 76, 20]. The element at the first index is 78.

method 1

In this approach we will loop through each query and perform operations based on the given query. We replace each element in the array with the next element to rotate it to the left, and each element with the previous element to rotate it to the right.

algorithm

Step 1- Start looping through each query.

Step 2− If query[p][0] is equal to 0, please follow the steps below.

Step 2.1- Initialize the "temp" variable using the first element of the array.

Step 2.2- Start traversing the array and replace each element with the next element.

Step 2.3- Replace the last element with the "temp" value.

Step 3− If query[p][0] is equal to 1, follow the steps below.

Step 3.1- Store the last element of the array in the "temp" variable.

Step 3.2- Start traversing the array and replace each element with the previous element.

Step 3.3- Update the first element with the "temp" value.

Step 4 - If requests[p][0] is 2, update the array element at the given index with the given value.

Step 5 - If requests[p][0] is 3, print the array value at the given index.

Example

#include <bits/stdc++.h>
using namespace std;

void performQueries(int arr[], int N, vector<vector<int>> &queries) {
    int len = queries.size();
    for (int p = 0; p < len; p++) {
        // For left shift
        if (queries[p][0] == 0) {
            //    left shift array
            int temp = arr[0];
            for (int p = 0; p < N - 1; p++){
                arr[p] = arr[p + 1];
            }
            arr[N - 1] = temp;
        }
        // For the right shift
        else if (queries[p][0] == 1) {
            // Right shift array
            int temp = arr[N - 1];
            for (int p = N - 1; p > 0; p--){
                arr[p] = arr[p - 1];
            }
            arr[0] = temp;
        }
        // For updating the value
        else if (queries[p][0] == 2) {
            arr[queries[p][1]] = queries[p][2];
        }
        // For printing the value
        else {
            cout << arr[queries[p][1]] << " ";
        }
    }
}
int main() {
    int arr[] = {8, 9, 13, 44, 76, 67, 21, 51};
    int N = sizeof(arr) / sizeof(arr[0]);
    vector<vector<int>> queries;
    queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
    performQueries(arr, N, queries);
    return 0;
}

Output

13 223

Time complexity - O(N*K), traverse the query and rotate the array.

Space complexity - O(1), because we use constant space.

Method 2

In this method, we will use a deque to store the array elements. Afterwards, to rotate the array to the left, we can pop the previous element from the queue and push it to the end of the queue. Likewise, we can rotate the array in the right direction.

algorithm

Step 1 - Define the deque and push all array elements into the queue.

Step 2- Use a for loop to iterate through each query.

Step 3- To rotate the array to the left, remove the first element from the beginning of the queue and push it to the end of the queue.

Step 4 - To rotate the array in the correct direction, remove an element from the end of the queue and push that element to the beginning.

Step 5- Update the element or print the element value based on the given query.

Example

#include <bits/stdc++.h>
using namespace std;

void performQueries(int arr[], int N, vector<vector<int>> &queries) {
    // Queue to insert array elements
    deque<int> que;
    // Add elements to queue
    for (int p = 0; p < N; p++) {
        que.push_back(arr[p]);
    }
    // total queries
    int len = queries.size();
    for (int p = 0; p < len; p++) {
        // For left shift
        if (queries[p][0] == 0) {
            // Get the first element
            int temp = que[0];
            // Remove the first element
            que.pop_front();
            // Push element at the last
            que.push_back(temp);
        }
        // For the right shift
        else if (queries[p][0] == 1) {
            // Get the last element
            int temp = que[N - 1];
            // remove the last element
            que.pop_back();
            // Insert element at the start
            que.push_front(temp);
        }
        // For updating the value
        else if (queries[p][0] == 2) {
            que[queries[p][1]] = queries[p][2];
        }
        // For printing the value
        else {
            cout << que[queries[p][1]] << " ";
        }
    }
}
int main() {
    int arr[] = {8, 9, 13, 44, 76, 67, 21, 51};
    int N = sizeof(arr) / sizeof(arr[0]);
    vector<vector<int>> queries;
    queries = {{1}, {0}, {2, 4, 50}, {3, 2}, {2, 2, 223}, {3, 2}};
    performQueries(arr, N, queries);
    return 0;
}

Output

13 223	

Time complexity - O(N K) for inserting array elements into the queue.

Space Complexity - O(N) for storing elements into a deque.

The deque data structure allows us to perform left and right rotation operations in O(1) time. Therefore, it improves the efficiency of the code that executes a given query.

The above is the detailed content of Reorder and update array elements according to a given query. For more information, please follow other related articles on the PHP Chinese website!