Table of Contents
In this tutorial, we will see how to rotate an array be K positions.
Problem:
N=6 and k=2
If Arr[] = {1, 2, 3, 4, 5, 6} and k=2
then [rotated array](https://java2blog.com/search-element-in-sorted-and-rotated-array-java/ “rotated array”) will be  {5, 6, 1, 2,  3,  4}
Solution:
There are multiple ways to solve this problem.
Approach 1:
Move each number by 1 place and do it k times.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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; } |
Space complexity: o(1)
Complete Java program to rotate array by K positions:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
package org.arpit.java2blog; 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]+" "); } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
