Last Updated: 21 Oct, 2022
Array Rotation
Easy
Asked in company
You are given an array A of size N.
You are also given an integer X and a direction DIR. You need to rotate the array A by X positions in the direction specified by DIR.
DIR can be:
- 'LEFT': Rotate the array to the left by X positions.
- 'RIGHT': Rotate the array to the right by X positions.
Return the resulting rotated array.
For example:
Input :
A = [6, 2, 6, 1], X = 1, DIR = ‘LEFT’
Output :
2 6 1 6
Explanation: Rotate array ‘A’ to the left one time.
[6, 2, 6, 1] => [2, 6, 1, 6]
Input Format:
First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first line contains two integers, ‘N', ‘X’, and the string ‘DIR’.
The second line has ‘N’ integers denoting the array ‘A’.
Output Format:-
You must return the rotated array.
Note:-
You don’t need to print anything. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= X <= 10^9
‘DIR’ is an element of {‘LEFT’, ‘RIGHT’}
Time Limit: 1 sec
Approaches
Approach:
- First, we can see that performing the ‘X’ operation is the same as performing ‘X’%N operations, where ‘N’ is the size of the array.
- We can write a function to perform one ‘LEFT’ rotation and another function to perform one ‘RIGHT’ rotation.
- We can use these functions to rotate an array ‘X’ times by calling the function ‘X’ times.
- For LEFT rotation:
- Store A[0] in a temporary variable and shift all other elements to their immediate left.
- Update A[ N - 1 ] with the value stored in the temporary variable.
- For RIGHT rotation:
- Store A[ N - 1 ] in a temporary variable and shift all other elements to their immediate right.
- Update A[ 0 ] with the value stored in the temporary variable.
Algorithm:
Function void rotateLeft([int] A):
- Initialize an integer variable ‘temp’ with A[0].
- For ‘i’ from 1 to ‘N’-1:
- A[i-1] = A[i]
- A[N-1] = temp
Function void rotateRight([int] A):
- Initialize an integer variable ‘temp’ with A[‘N’-1].
- For ‘i’ from ‘N’ - 2 to 0:
- A[i+1] = A[i]
- A[0] = temp
Function [int] rotateArray([int] A, int X, string DIR):
- If DIR == ‘LEFT’:
- For ‘i’ from 0 to ‘X’ - 1:
- Call rotateLeft(A).
- For ‘i’ from 0 to ‘X’ - 1:
- Else If DIR == ‘RIGHT’:
- For ‘i’ from 0 to ‘X’ - 1:
- Call rotateRight(A).
- For ‘i’ from 0 to ‘X’ - 1:
- Return ‘A’
Approach:
- First, we can see that performing the ‘X’ operation is the same as performing ‘X’%N operations, where ‘N’ is the size of the array.
- We can observe that for the right rotation, the final array after the ‘X’ rotation is the same as the array after the following three steps-
- We are reversing the whole array once.
- We are reversing the first ‘X’ elements.
- We are reversing the rest of the ‘N’-’X’ elements.
- For example, [1, 2, 3, 4, 5] after 2 right rotations will be [4, 5, 1, 2, 3].
- Step 1: [1, 2, 3, 4, 5] => [5, 4, 3, 2, 1].
- Step 2: [5, 4, 3, 2, 1] => [4, 5, 3, 2, 1].
- Step 1: [4, 5, 3, 2, 1] => [4, 5, 1, 2, 3].
- Hence, we can perform the right operation in O(N).
- Similarly, we can observe that for the left rotation, the final array after the ‘X’ rotation is the same as the array after the following three steps-
- We are reversing the whole array once.
- We are reversing the first ‘N’-’X’ elements.
- We are reversing the rest of the ’X’ elements.
- For example, [1, 2, 3, 4, 5] after 2 left rotations will be [3, 4, 5, 1, 2].
- Step 1: [1, 2, 3, 4, 5] => [5, 4, 3, 2, 1].
- Step 2: [5, 4, 3, 2, 1] => [3, 4, 5, 2, 1].
- Step 1: [3, 4, 5, 2, 1] => [3, 4, 5, 1, 2].
- Hence, we can perform the left operation in O(N).
Algorithm:
Function void rotateLeft([int] A, int X):
- reverse( A.begin(), A.end() ).
- reverse( A.begin(), A.begin()+X)
- reverse( A.begin()+X, A.end())
Function void rotateRight([int] A, int X):
- reverse( A.begin(), A.end() ).
- reverse( A.begin(), A.begin() + ( N - X ) )
- reverse( A.begin() + ( N - X ), A.end())
Function [int] rotateArray([int] A, int X, string DIR):
- If DIR == ‘LEFT’:
- Call rotateLeft(A, X).
- Else If DIR == ‘RIGHT’:
- Call rotateRight(A, X).
- Return ‘A’
Similar problems