## Wednesday, May 4, 2022

### Question 33 : Rotate an array by K positions

For example :

``````N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then rotated array will be  {5, 6, 1, 2,  3,  4}``````

#### Approach 1:

Move each number by 1 place and do it k times.

``````public static int[] rotateBruteForce(int[] nums, int k) {
for (int i = 0; i < k; i++) {
for (int j = nums.length - 1; j > 0; j--) {
// move each number by 1 place
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}
System.out.println("Array rotation after "+(i+1)+" step");
printArray(nums);
System.out.println();
}
return nums;
}
``````

Time complexity: o(n*k)
Where n is number of elements and k denotes position shift.
Space complexity: o(1)

#### Approach 2:

You can rotate the array using temp array in o(n) :

``````public static int[] rotateExtraSpace(int[] nums, int k)
{
int n=nums.length;
if(k > n)
k=k%n;

int[] result = new int[n];

for(int i=0; i < k; i++){
result[i] = nums[n-k+i];
}

int index=0;
for(int i=k; i<n; i++){
result[i] = nums[index++];
}
return result;
}``````

Time complexity: o(n)
Space complexity: o(n)

#### Approach 3:

This is the most optimized approach.
Algorithm for this approach works as below:

• Reverse whole array.
• Reverse first k elements
• Reverse rest n-k elements.
For example:
let’s say Array is {1,2,3,4,5,6,7,8}
You want to rotate by k position.
It will work as below:

• You rotate the whole array. So array became: {8,7,6,5,4,3,2,1}
• Reverse first k elements, so array became : {7,8,6,5,4,3,2,1}
• Reverse rest of elements, so array became  : {7,8,1,2,3,4,5,6}
Java code:

:

``````public static int[] rotateOptimized(int[] nums,int k)
{
int n=nums.length;
if(k > n)
k=k%n;
nums=reverse(nums,0,n-1);
nums=reverse(nums,0,k-1);
nums=reverse(nums,k,n-1);
return nums;
}
public static int[] reverse(int[] nums,int start,int end)
{

while (start <= end ) {
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
return nums;
}``````
Time complexity: o(n)
Space complexity: o(1)

### Complete Java program to rotate array by K positions:

``````public class RotateArrayMain {

public static void main(String[] args)
{
int nums[]={1,2,3,4,5,6,7,8};

System.out.println("Rotate array by shifting one elements by 1 and do it k times");
int[] result1=rotateBruteForce(nums,2);
System.out.println("Final rotated array :");
printArray(result1);
System.out.println();
System.out.println("================================");
System.out.println("Rotate array using extra space");

int nums2[]={10,20,30,40,50,60};
int[] result2=rotateExtraSpace(nums2,5);
printArray(result2);
System.out.println();
System.out.println("================================");
System.out.println("Rotate array most optimized approach");
int nums3[]={1,2,3,4,5,6,7,8,9,10};
int[] result3=rotateOptimized(nums3,4);
printArray(result3);
}

public static int[] rotateBruteForce(int[] nums, int k) {
int n=nums.length;
if(k > n)
k=k%n;
for (int i = 0; i < k; i++) {
for (int j = n - 1; j > 0; j--) {
// move each number by 1 place
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = temp;
}
System.out.println("Array rotation after "+(i+1)+" step");
printArray(nums);
System.out.println();
}
return nums;
}

public static int[] rotateExtraSpace(int[] nums, int k)
{
int n=nums.length;
if(k > n)
k=k%n;

int[] result = new int[n];

for(int i=0; i < k; i++){
result[i] = nums[n-k+i];
}

int index=0;
for(int i=k; i<n; i++){
result[i] = nums[index++];
}
return result;
}

public static int[] rotateOptimized(int[] nums,int k)
{
int n=nums.length;
if(k > n)
k=k%n;
nums=reverse(nums,0,n-1);
nums=reverse(nums,0,k-1);
nums=reverse(nums,k,n-1);
return nums;
}
public static int[] reverse(int[] nums,int start,int end)
{

while (start <= end ) {
int temp=nums[start];
nums[start]=nums[end];
nums[end]=temp;
start++;
end--;
}
return nums;
}

public static void printArray(int []arr)
{
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
``````
When you run above program, you will get below output:

``````Rotate array by shifting one elements by 1 and do it k times
Array rotation after 1 step
8 1 2 3 4 5 6 7
Array rotation after 2 step
7 8 1 2 3 4 5 6
Final rotated array :
7 8 1 2 3 4 5 6
================================
Rotate array using extra space
20 30 40 50 60 10
================================
Rotate array most optimized approach
7 8 9 10 1 2 3 4 5 6``````

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.