Rotate array

Easy
0/40
Average time to solve is 25m
profile
Contributed by
839 upvotes
Asked in companies
Deutsche BankIBMSalesforce

Problem statement

Given an array 'arr' with 'n' elements, the task is to rotate the array to the left by 'k' steps, where 'k' is non-negative.


Example: 
'arr '= [1,2,3,4,5]
'k' = 1  rotated array = [2,3,4,5,1]
'k' = 2  rotated array = [3,4,5,1,2]
'k' = 3  rotated array = [4,5,1,2,3] and so on.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'n' representing the size of the array.

The second line contains 'n' space-separated integers representing the elements of the array.

The last line contains an integer 'k' representing the number of times the array has to be rotated in the left direction.
Output Format: 
The output contains 'n' space-separated integers representing the Rotated array elements.
Note:- 
You don’t need to print anything. Just implement the given function.
Sample Input 1:
8
7 5 2 11 2 43 1 1
2
Sample Output 1:
2 11 2 43 1 1 7 5
Explanation of Sample Input 1:
Rotate 1 steps to the left: 5 2 11 2 43 1 1 7
Rotate 2 steps to the left: 2 11 2 43 1 1 7 5
Sample Input 2:
4
5 6 7 8
3
Sample Output 2:
8 5 6 7
Explanation of Sample Input 2:
Rotate 1 steps to the left: 6 7 8 5
Rotate 2 steps to the left: 7 8 5 6
Rotate 2 steps to the left: 8 5 6 7
Expected Time Complexity:
O(n), where ‘n’ is the size of the array ‘arr’ and ‘k’ is the number of rotations.
Constraints:
1 <= 'n' <= 10^3
1 <= 'arr'[i] <= 10^9
1 <= 'k' < 'n'


Hints:
1. For an index ‘i’, find where it lands after k swaps.
2. When performing rotation once observe how the positions of all elements change.
Approaches (2)
Naive Approach
  • We rotate the array ‘k’ times where in each iteration, we rotate the array by 1.
  • Rotating the array once can be done by changing ‘arr’[i] to ‘arr’[i+1] and appending the first character to the end.
Time Complexity

O(n*k), where ‘n’ is the size of the array ‘arr’ and ‘k’ is the number of rotations.

 

We are doing a total of ‘k’ iterations where each iteration contributes O(n).

 

Hence the time complexity is O(n*k). 

Space Complexity

O(1).

 

We are not using any extra space.

 

Hence the space complexity is O(1). 

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Rotate array
Full screen
Console