Left Rotations of An Array
You are given an array consisting of 'N' elements and you need to perform 'Q' queries on the given array. Each query consists of an integer which tells the number of elements by which you need to left rotate the given array. For each query return the final array obtained after performing the left rotations.

Note:

Perform each query on the original array only i.e. every output should be according to the original order of elements.

Example:

Let the array be [1, 2, 3, 4, 5, 6] and the queries be {2, 4, 1}. For every query, we’ll perform the required number of left rotations on the array. For the first query, rotate the given array to the left by 2 elements, so the resultant array is: [3, 4, 5, 6, 1, 2]. For the second query, rotate the given array to the left by 4 elements, so the resultant array is: [5, 6, 1, 2, 3, 4]. For the third query, rotate the given array to the left by 1 element, so the resultant array is: [2, 3, 4, 5, 6, 1].

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains two space-separated integers ‘N’ and ‘Q’ denoting the number of elements present in the array and the number of queries to be performed on the given array, respectively. The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array. The third line of every test case contains ‘Q’ space-separated integers denoting the queries.

Output format:

For every query of each test case, return ‘N’ space-separated integers which denote the resultant array after performing the rotation.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Left Rotations of An Array

You are given an array consisting of 'N' elements and you need to perform 'Q' queries on the given array. Each query consists of an integer which tells the number of elements by which you need to left rotate the given array. For each query return the final array obtained after performing the left rotations.

Note:

Perform each query on the original array only i.e. every output should be according to the original order of elements.

Example:

Let the array be [1, 2, 3, 4, 5, 6] and the queries be {2, 4, 1}. For every query, we’ll perform the required number of left rotations on the array.

For the first query, rotate the given array to the left by 2 elements, so the resultant array is: [3, 4, 5, 6, 1, 2].

For the second query, rotate the given array to the left by 4 elements, so the resultant array is: [5, 6, 1, 2, 3, 4].

For the third query, rotate the given array to the left by 1 element, so the resultant array is: [2, 3, 4, 5, 6, 1].

Input format:

The very first line of input contains an integer ‘T’ denoting the number of test cases. 

The first line of every test case contains two space-separated integers ‘N’ and ‘Q’ denoting the number of elements present in the array and the number of queries to be performed on the given array, respectively. 

The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the array.

The third line of every test case contains ‘Q’ space-separated integers denoting the queries.

Output format:

For every query of each test case, return ‘N’ space-separated integers which denote the resultant array after performing the rotation.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10 
1 <= N <= 1000
1 <= Q <= 100
0 <= Queries[i] <= 10^5
-10^5 <= Array[i] <= 10^5

Where 'Queries[i]' denotes the extent to which the array in each query needs to be rotated and 'Array[i]' denotes the array element.

Time limit: 1 sec

Accepted Answer

Rotate One Element At A Time

The idea is to create a function which would rotate the array one element at a time. This can be done by shifting the array towards left by one element and copying the first element to the end of the array. For every query repeatedly call the above function, until the desired rotation is obtained.

If the number of rotations required, say ‘K’, is greater than the number of elements, ‘N’, then the effective number of rotations will be ‘K’ % ‘N’. This is due to the fact that rotating the array by its size results in the same array.

An important point to note here that for every query, we need to perform the rotations on a temporary copy of the original array, so as to avoid any modifications on the original one. This is because we want to obtain the rotations of the original array, hence, we need the original array to remain unchanged.

Space Complexity: O(n)Explanation:

O(N).

Since O(N) extra space is required for storing the temporary array. Hence the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * K * Q), Where ‘N’ is the number of elements in the array, ‘Q’ is the number of queries and ‘K’ is the maximum number of rotations required, considering all the queries.

Since we rotate the array by K elements, each rotation requires N operations. Also, N operations to copy the original array into a temporary array. Hence the overall time complexity for Q queries will be O((N + N) * K * Q) = O(N * K * Q).

Accepted Answer

Rotate Blocks of Array

Instead of rotating the array one element at a time, a complete block of array can be rotated. Suppose for a given query we need to output the array obtained after ‘K’ left rotations.

We can achieve this as follows:

Reverse the first ‘K’ elements - [0, ‘K’ - 1].
Reverse the last ‘N’ - ‘K’ elements - ['K', ‘N’].
Now, reverse the complete array - [0, ‘N’ - 1].

We can call the above procedure once for every query to get the desired result. If the number of rotations required, say ‘K’, is greater than the number of elements, 'N', then the effective number of rotations will be ‘K’ % ‘N’. This is due to the fact that rotating the array by its size results in the same array.

An important point to note here that for every query, we need to perform the rotations on a temporary copy of the original array, so as to avoid any modifications on the original one. This is because we want to obtain the rotations of the original array, hence, we need the original array to remain unchanged.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of elements in the array.

Since extra space is required for storing the temporary array in O(N) space. And hence the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * Q), Where ‘N’ is the number of elements in the array, ‘Q’ is the number of queries.

Since each rotation requires N operations to copy the original array into a temporary array, and N operations to perform the actual rotation. Hence the overall time complexity for Q queries will be O((N + N) * Q) = O(N * Q).

Accepted Answer

Using a Temporary Array

The previous approaches required us to perform actual rotations for every query. Also in order to avoid any modifications to the original array, we needed to copy the original array into a temporary array. This can be avoided if simply use the indices to generate the rotated array.

The idea is to create a temporary array, say ‘Temp’, of size 2 * ‘N’, which will help us handle the queries quickly. Now, copy the entire array into the temporary array, two times.

Suppose for a given query we need to output the array obtained after ‘K’ left rotations. So, the first element in the rotated array would be present at the index ‘K’ % ‘N’ in the temporary array. And the last element in the rotated array would be present at the index ('K' % ‘N’ + ‘N’) in the temporary array. Therefore, the subarray ‘Temp[K % N, K % N + N]’ gives us the desired result.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of elements in the array.

Since extra space is required for the temporary array of size 2 * N. Hence the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * Q), Where ‘N’ is the number of elements in the array and ‘Q’ is the number of queries.

Since the task to find the starting and ending indices of the rotated array takes O(1) time. Also, N operations to print the found subarray. Hence the overall time complexity for Q queries will be O(N * Q).

Accepted Answer

O(1) Space Approach

Instead of using a temporary array of size 2 * ‘N’, we can generate the rotated array directly from the given array, using just the indices.

Suppose for a given query we need to output the array obtained after ‘K’ left rotations.

So, the first element in the rotated array would be present at the index ‘K" % ’N' in the original array.
Now, copy the elements starting from the index ‘K’ % ‘N’ into another array.
On reaching the end of the array, again start from the 0th index until you reach back to index ‘K’ %'N'.
Therefore, the subarray Array['K' % ‘N’, ‘N’] followed by Array[0, ‘K’ %' N' - 1] gives us the desired result.
Add the resulting array to the answer.

Space Complexity: O(1)Explanation:

O(1).

Since no extra space is required, hence the space complexity will be O(1).

Time Complexity: OtherExplanation:

O(N * Q), Where ‘N’ is the number of elements in the array and ‘Q’ is the number of queries.

Since the task to find the starting and ending indices of the rotated array takes O(1) time. Also, N operations to print the found subarray. Hence the overall time complexity for Q queries will be O(N * Q).

Note:

Example:

Input format:

Output format:

Note:

Constraints:

Top Tech Vedika Software Engineer interview questions & answers

Popular interview questions of Software Engineer