Array Rotation

Easy
0/40
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in company
TCS

Problem statement

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]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 1 LEFT
1 2 3 4
6 2 RIGHT
1 2 4 3 5 6
Sample Output 1 :
2 3 4 1
5 6 1 2 4 3
Explanation Of Sample Input 1 :
For test case one:

Input :
A = [1, 2, 3, 4], X = 1, DIR = ‘LEFT’

Output :
2 3 4 1

Explanation: Rotate array ‘A’ to the left one time.
[1, 2, 3, 4] => [2, 3, 4, 1]

For test case two:

Input :
A = [1, 2, 4, 3, 5, 6], X = 2, DIR = ‘RIGHT’

Output :
5 6 1 2 4 3

Explanation: Rotate array ‘A’ to the right one time.
[1, 2, 4, 3, 5, 6] => [6, 1, 2, 4, 3, 5]
Sample Input 2 :
2
6 3 LEFT
22 8 4 7 5 10
6 2 RIGHT
9 3 1 6 3 9
Sample Output 2 :
7 5 10 22 8 4 
3 9 9 3 1 6
Hint

Observe how the element's position changes after rotation.

Approaches (2)
Brute Force

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):

  1. Initialize an integer variable ‘temp’ with A[0].
  2. For ‘i’ from 1 to ‘N’-1:
    • A[i-1] = A[i]
  3. A[N-1] = temp


 

    Function void rotateRight([int] A):

  1. Initialize an integer variable ‘temp’ with A[‘N’-1].
  2. For ‘i’ from ‘N’ - 2 to 0:
    • A[i+1] = A[i]
  3. A[0] = temp


 

    Function [int] rotateArray([int] A, int X, string DIR):
 

  1. If DIR == ‘LEFT’:
    • For ‘i’ from 0 to ‘X’ - 1:
      • Call rotateLeft(A).
  2. Else If DIR == ‘RIGHT’:
    • For ‘i’ from 0 to ‘X’ - 1:
      • Call rotateRight(A).
  3. Return ‘A’
Time Complexity

O( N * X ), Where ‘N’ is the size of the array ‘A’ and ‘X’ is the number of rotations. 

 

We are taking O( N ) to perform one rotation. We take O( N * X ) time to achieve' X' rotations. Hence, the overall complexity will be O( N * X ).

Space Complexity

O( 1 ). 

 

We are using constant extra space. So, the Space Complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Array Rotation
Full screen
Console