How to Rotate an Array in Java | Tekolio
In this blog, we will learn what exactly array rotation is? And how to rotate an array either in the left or the right direction. Here rotation only means shifting the elements of the array in the desired direction.
Input : Arr = [1, 2, 3, 4, 5]k=2Output : Arr = [4, 5, 1, 2, 3]
Initially, the array was [1, 2, 3, 4, 5], if we rotate the array once (k=1) towards the right, the element will shift from the index 0 to index 1 Similarly, we need to shift all elements towards the right, which means the last element will end up with at the first position.
Now after the first rotation — Arr = [5, 1, 2, 3, 4]
If we rotate on more time — Arr = [4, 5, 1, 2, 3] -> k = 2
Similarly, if we want to rotate the array towards the left. In that case, we have to shift the elements to the left, the element will shift from index 1 to index 0, and the other elements as well making the first element the last element of the array.
How to solve it
There are many kinds of approaches, but we will only be seeing two approaches in this blog They are -
- Using the temp array
- By reversing the Array
Approach 1 — By using the Temp Array
The idea is simple, we will create a new array of size k and store the elements equal to k from either start or the end of the array depending upon the type of rotation we are doing, and then put them back in the original array where they were supposed to be placed after rotation. Check the example given below in which we are rotating k times towards left, to understand the approach better.
Input arr = [1, 2, 3, 4, 5]
k = 2
- Store the first k elements in a temp array: temp = [1, 2]
- Shift rest of the elements(according to the given data/ question): arr = [3, 4, 5,]
- Store back the k elements: arr = [3, 4, 5, 1, 2]
- Create a new array called temp of length k — the number of times we have to rotate the array
- Store either the first k elements or the last k elements depending upon the type of rotation
- Move the rest of the elements either towards the 0th index or the last index.
- Copying the elements stored from the temp array to the original array at their respective indexes.
A = [3, 4, 5, 1, 2]
Time complexity: O(N), Auxiliary Space: O(N)
In the above code, we have used System.arraycopy method to copy the k elements from the array and put them back at their desired position after rotation.
The code discussed above is for rotating the array towards the left, we can also do the same thing for rotating the array in the right direction as well, we just have to change the index numbers in both the loop and the System.arraycopy method as shown.
Method 2 — By Reversing the Array
The idea is to first reverse the whole array and then reverse it again but in parts. The first part will be from the 0th index till the kth index while the second part contains the rest of the elements.
Input : A = [1, 2, 3, 4, 5], k=2Reversing the whole array — A = [5, 4, 3, 2, 1]Reversing in parts — A = [4, 5, 1, 2, 3]
Here we are not using any additional space like in the above code, thus the space complexity becomes O(1) while the time complexity remains unchanged.
- Reverse the whole Array
- Divide the array into two parts, from 0 to k-1 and from k to n-1
- Reverse these two parts individually and we have our rotated array
A = [3, 4, 5, 1, 2]
Time Complexity: O(n) Auxiliary Space: O(1)
We have already discussed the approach in brief, and it is also clear from the code itself that we are reversing the array two times, a full reversal at the beginning and a reversal by parts at the end to get our desired array.
And for that, we have created a separate class called rotateArray that deals with the reversing part of the program. This class takes three parameters -
- The original array
- The starting index
- The ending index
Which we have provided it from the main class from which we have called this class for all the three conditions of reversing the whole array to rotate it towards the left.
What if we want to rotate the array in the right direction?
We have to first deal with reversing the array in parts and then reverse the whole array to get the desired array. Check the code below -
In this blog, we have seen what it means to rotate an array and how many types of array rotations are there with different ways to do each of them.
There can be many more strategies out there through which this question can be solved, but the minimum time complexity and the space complexity will always be O(n) and O(1) as we do have to traverse the array once to shift all the elements either towards the right or left depending upon which type of rotation we are doing.
This question was asked by many tech companies like Microsoft and Amazon and also can become pretty difficult sometimes if the value of k exceeds the length of the array or is negative.
Originally published at https://tekolio.com on May 30, 2022.
20+ Array Coding Problems and Questions from Programming Interviews
Hello guys, An array is the most fundamental data structure, which stores elements at a contiguous memory location. It…
Top 21 String Programming Interview Questions for Beginners and Experienced Developers
Along with array, binary tree, and linked list data structures, the string is another popular topic on programming job…