ARRAY ROTATION

Array Rotation

Problem : Given an array, rotate the array to the left by k steps, where k is non-negative.

Today, we’re going to solve the array rotation problem. We will start with a simple solution and move to a more optimized one.

Example :

For the array : [1,2,3,4,5,6,7] and k = 5, the rotated array is [6,7,1,2,3,4,5].

Edge case :

(i) If k is equal then there is no need to rotate the array.

(ii) If k is greater than or equal to the length of the array then, k = k % arrayLength . If k=9 in the above case, after 7 rotation the elements of the array becomes back to the original position and 2 extra rotations will give you the answer. So instead of considering k as 9, we will consider it as 2.

Approach 1:

This is the simplest approach. In this approach, we will rotate the array one by one.

Time Complexity :

O(arrayLength * k)

Space Complexity :

O(1)

Approach 2:

In this approach, we are going to use a temp array to store values till k elements.

Time Complexity :

O(arrayLength)

Space Complexity :

O(k)

Approach 3:

In this approach, we are going to use the juggling algorithm. In this method, we divide the array into ‘m’ no: of sets where ‘m’ is the gcd of ‘array length’ and ‘k’. And then we rotate the elements of each set.

Time Complexity :

O(arrayLength)

Space Complexity :

O(1)

Approach 4:

In this approach, we are going to use the block swap algorithm.

Steps:-

1. Create two arrays A and B where A is from 0 to k-1 and B is from k to n.

2. If the size of A is smaller than B then divide array B into two parts Bl and Br such that the size of Br is equal to the size of A. Then perform swap operation on A and B2. Hence, the array becomes BrBlA.

3. If the size of B is smaller than A then divide array A into two parts Al and Ar such that the size of Al is equal to the size of B. Then perform swap operation on Al and B. Hence, the array becomes BArAl.

4. This process is continued till the size of A and B is the same.

5. And then a final swap is performed.

Time Complexity :

O(arrayLength)

Space Complexity :

O(1)

Approach 5:

In this approach, we are going to use the reversal algorithm.

Steps:-

1. Create two arrays A and B where A is from 0 to k-1 and B is from k to n.
2. Reverse A
3. Reverse B
4. Reverse the whole array

Time Complexity :

O(arrayLength)

Space Complexity :

O(1)

Output :

Original Array
[1, 2, 3, 4, 5, 6, 7]
Reversed Array
[6, 7, 1, 2, 3, 4, 5]

Code Links

Approach 1 -https://repl.it/@Sapna2001/arrayRotation1

Approach 2 -https://repl.it/@Sapna2001/arrayRotation2

Approach 3 -https://repl.it/@Sapna2001/arrayRotation3

Approach 4 -https://repl.it/@Sapna2001/arrayRotation4

Approach 5 -https://repl.it/@Sapna2001/arrayRotation5

That’s it from my side. I hope you enjoyed reading this article 😊.

If you want to get connected with me, please follow these links :

LinkedIn -https://www.linkedin.com/in/sapna2001/

Github -https://github.com/Sapna2001

Website -https://sapna2001.github.io/Portfolio/

Quora -https://www.quora.com/profile/Sapna-191

Blogs -https://sapna2001.github.io/Portfolio/html/blogs.html

And if you have any suggestions, feel free to get in touch with me over LinkedIn & the comment section is also all yours.

If you liked this story, hit the clap button as it motivates me to write more & better.

Thanks for reading!!!!