Table of Contents

Toggle## Problem Statement

Given an array, rotate the array to the left by `k`

steps, where `k`

is non-negative.

**Example**

`Input:`

array = [1,2,3,4,5,6,7], k = 3

`Output:`

[4,5,6,7,1,2,3]

`Explanation:`

array rotation to the right after 1 step: [2,3,4,5,6,7,1]

array rotation to the right after 2 steps: [3,4,5,6,7,1,2]

array rotation to the right after 3 steps: [4,5,6,7,1,2,3]

## Array Rotation : Using Extra Space

### Algorithm

`Input arr=[1,2,3,4,5,6,7], k=3`

**Step 1:** Store first k elements in auxiliary array

arr=[*,*,*,4,5,6,7], auxiliary_array=[1,2,3] ***Step 2:** Shift rest of the elements of array to left by k

arr=[4,5,6,7, , ,], auxiliary_array=[1,2,3]**Step 3:** Store back the auxiliary arrays's k element

arr=[4,5,6,7,1,2,3]

### Complexity

**Time complexity :** O(n) **Auxiliary Space : **O(k)

### Implementation

// Array Rotation using extra space public static int[] leftRotate(int[] arr, int k) { // get the length of the array int n = arr.length; // To handle cases if k>n k = k % n; // construct an auxiliary array of size k and // fill it with the first k elements of the input array int[] aux = new int[k]; for (int i = 0; i < k; i++) { aux[i] = arr[i]; } // shift the remaining n-k elements of the input array at the beginning for (int i = k; i < n; i++) { arr[i - k] = arr[i]; } // put the elements of the auxiliary array at their // correct positions in the input array for (int i = n - k; i < n; i++) { arr[i] = aux[i - (n - k)]; } return arr; }

## Rotate Element One by One

### Algorithm

`Input arr=[1,2,3,4,5,6,7], k=3`

**Step 1:** Store arr[0] in a temporary temp variable *arr=[1,2,3,4,5,6,7], temp=1* **Step 2:** Move rest of the elements of array to left by 1 *arr=[2,3,4,5,6,7,_], temp=1* **Step 3:** Finally put temp variable to last(arr[n-1]) *arr=[2,3,4,5,6,7,1], temp=1* **Step 4:** Repeat the above steps k times

*arr=[4,5,6,7,1,2,3]*### Complexity

**Time complexity :** O(n * d) **Auxiliary Space :** O(1)

### Implementation

// Array Rotation One by One int[] leftRotateOneByOne(int arr[], int k) { int n = arr.length; k=k%n; for (int i = 0; i < k; i++) { int temp = arr[0]; for (int j = 0; j < n - 1; j++) { arr[j] = arr[j + 1]; } arr[n - 1] = temp; } return arr; }

## Juggling Algorithm

### Algorithm

`Divide the array into M sets, where M = GCD (n, k), then rotate the items inside each set. `

The GCD(n, k) number of blocks is calculated using the array's element count (n) and the number of rotations (k) to be performed on the array.

Shifting will then occur in each block to the matching elements in the block.

After all of the items in all of the blocks have been relocated, the array will be rotated for the amount of times specified.

Let’s apply this to above example.

`M = GCD(12, 3) = 3; Initial Array : 1 2 3 4 5 6 7 8 9 10 11 12`

Elements are first moved in first set: **4** 2 3 **7** 5 6 **10 **8 9 **1** 11 12

Second Set Moves : 4 **5** 3 7 **8** 6 10 **11** 9 1 **2** 12

Third Set Moves : 4 5 **6** 7 8 **9** 10 11 **12** 1 2`3`

** **

### Complexity

**Time complexity :** O(n) **Auxiliary Space :** O(1)

### Implementation

// Array Rotation using JugglingAlgorithm void jugglingAlgorithm(int arr[], int d) { int n = arr.length; d = d % n; int i, j, k, temp; int blocks = gcd(d, n); // Loop through each set for (i = 0; i < blocks; i++) { temp = arr[i]; j = i; while (true) { k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } arr[j] = temp; } } // Function to get gcd of a and b int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); }

## Reversal Algorithm

### Algorithm

`Let AB are the two parts of the input array where A = arr[0..k-1] and B = arr[k..n-1]. The idea of the algorithm is : `

Input arr[] = [1, 2, 3, 4, 5, 6, 7], k =3 and n = 7

**Step1: **Reverse A to get ArB, where Ar is reverse of A. *arr= [3, 2, 1, 4, 5, 6, 7], A=[1,2,3], B=[4,5,6,7] ***Step2:** Reverse B to get ArBr, where Br is reverse of B.

*arr= [3, 2, 1, 7, 6, 5, 4], A=[1,2,3], B=[4,5,6,7]*

**Reverse all to get (ArBr)r = BA.**

Step3:

Step3:

*arr= [4, 5, 6, 7, 1, 2, 3], A=[1,2,3], B=[4,5,6,7]*

### Complexity

**Time complexity :** O(n) **Auxiliary Space :** O(1)

### Implementation

// Array Rotation using Reversal Algorithm static void reversalAlgorithm(int arr[], int k) { if (k == 0) return; int n = arr.length; k = k % n; reverse(arr, 0, k - 1); reverse(arr, k, n - 1); reverse(arr, 0, n - 1); } // Function to reverse an array static void reverse(int arr[], int start, int end) { int temp; while (start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } }

## Conclusion

In this article we discussed various algorithms for array rotation. And the best algorithms for array rotation based on time and space complexity are Juggling and Reversal Algorithm with time complexity of O(n) and with O(1) auxiliary space.

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!