Java Rotate Array - From Right

Hi, welcome to my blog.

Today we will learn how to rotate an array from the right.
Consinder the array [1,2,3,4,5,6,7], rotate k = 3 steps.
The output will be [5,6,7,1,2,3,4].
There are many ways of solving this.
First, I will show you what I would refer to as "less optimal solution", because we will use an extra sapce. Then I will show you a more optimal solution.

1. Less optmal solution - extra space O(n) , run time O(n).

We are going to loop n times, every loop we will swap two numbers.
That is, index [i] and index j = i+k%array.length.
You should figure out why i+k%array.length.
/**
*
* i=0 to i = 6, k=3 [swap i = 0 and j = 3].
* So, why j = 3?
* i=0, j=(i+k%array.length)
* So, why are we doing this? Please think about it.
*                                   1,2,3,4,5,6,7
* i=0,j=(0+3=3 %7=3 ->*,*,*,1,*,*,*
* i=1,j=(1+3=4 %7=4 ->*,*,*,1,2,*,*
* i=2,j=(2+3=5 %7=5 ->*,*,*,1,2,3,*
* i=3,j=(3+3=6 %7=6 ->*,*,*,1,2,3,4
* i=4,j=(4+3=7 %7=0 ->5,*,*,1,2,3,4
* i=5,j=(5+3=8 %7=1 ->5,6,*,1,2,3,4
* i=6,j=(6+3=9 %7=2 ->5,6,7,1,2,3,4
*
*/


Sample code.

public static void rotate2(int[] nums, int k) {
System.out.println(Arrays.toString(nums));
int n = nums.length;
int[] temp = Arrays.copyOf(nums, n);
for(int i=0;i nums[(i+k) % n] = temp[i];
}
}


2. More optimal solution, not extra space, run time O(n).
This solution is quite straightforward.
We will swap number by calling a function.
First, swap [0 to 2], or until i < array.length in every loop we will increment i and decrement array.length which we will store in a local variable.
/**
* ### 0 to n-1(6)
* 1,2,3,4,5,6,7
* 1. 7,2,3,4,5,6,1 --> start =0,end=6
* 2. 7,6,3,4,5,2,1 --> start =1,end=5
* 3. 7,6,5,4,3,2,1 --> start =2,end=4
* This will not execute --> start =3,end=3 ==
* output = 7,6,5,4,3,2,1
* ### 0 to k-1(2)
* 7,6,5,4,3,2,1
* 1. 5,6,7,4,3,2,1 --> start =0,end=2
* This is not execute == start=1,end=1
* ### 3 to n-1(6)
* 5,6,7,4,3,2,1
* 1. 5,6,7,1,3,2,4 --> start=3,end=6
* 2. 5,6,7,1,2,3,4 --> start=4,end=5
* This will not execute, start=5,end=4
**/


Sample code.

public static void rotate(int[] nums, int k) {
/**
* when we do array.length, we get the length from JVM heap
* if we stored the value in a primitive variable,(stack)
* this would mean faster access,
* but this is trivial/little significance.
*/
if(nums.length == 1)
return;
k = k % nums.length; This line is very important... when k is > array.length
swap(nums, 0, nums.length-1);
swap(nums, 0, k-1);
swap(nums, k, nums.length-1);
}


private static void swap(int[] arr, int start, int end){
//[1,2,3,4,5,6,7] s=0,e=6
while(start < end){
int temp = arr[start];//1
arr[start] = arr[end];//swap first, 1 with last, 7
arr[end] = temp;//first, 1 to last
start++;
end--;
}
}




Note: left rotation using the last method would be very simple.
Just change the below lines ...

swap(a, 0 , n-1);
swap(a, n-k , n-1);
swap(a, 0 , n-k-1);


Where..
a is the input array, like nums
and
int n = a.length;
and
k = k % a.length;




Thanks for reading...