# Array Circular Shift

The problem is to rotate elements in an array in a circular way. For example, shifting the array

`{38, 27, 43, 3, 9, 82, 10}`

3 positions to the left produces

`{3, 9, 82, 10, 38, 27, 43}`

Using a loop we can shift elements one position to the left.

public static void shift(int[] arr) { int tmp = arr[0]; for (int i = 1; i < arr.length; i++) arr[i - 1] = arr[i]; arr[arr.length - 1] = tmp; }

Using a nested loop, we can shift elements k position to the left.

public static void shift(int[] arr, int k) { k = k % arr.length; while (k-- > 0) { int tmp = arr[0]; for (int i = 1; i < arr.length; i++) arr[i - 1] = arr[i]; arr[arr.length - 1] = tmp; } }

For an array of length n, the running time of the nested loop above is O(n^2), since k in general is in the order of n.

The following algorithm solves the problem in linear time O(n). It does the following: (1) reverse the array; (2) reverse the first n-k elements; (3) reverse the last k elements. The first step moves the first k elements move to the end, and the next two steps put elements in the right order.

public static void shift(int[] arr, int k) { int n = arr.length; k = k % n; reverse(arr, 0, n - 1); reverse(arr, 0, n - k - 1); reverse(arr, n - k, n - 1); } public static void reverse(int[] arr, int start, int end) { while (start < end) { int tmp = arr[start]; arr[start] = arr[end]; arr[end] = tmp; start++; end--; } }