Rotate an Array

Algorithm/Insights

Naive Solution: Rotate array by one element k times
Algorithm to rotate array by one element:
1. Take a temporary variable to store first element of the array.
2. Shift all elements by 1 position on the left, overwriting the first element of the array.
3. Set last element of array to the first element saved in temporary variable.
This is rotation by 1 element.
By invoking this k times, we get array rotated k times.
Time Complexity: O(n*k)
Space Complexity: O(1)

Solution using Temporary Array:
1. Move first k elements of the array to a temporary array.
2. Shift all the elements of the array from k+1 to end of array to the beginning of the array.
3. Copy the k elements in temporary array to the last k positions of the original array.
Time Complexity: O(n)
Space Complexity: O(k)

Efficient Solution: Using Array Reversal
1. Reverse the array elements from 0 to k-1.
2. Reverse the array elements from k to array.length-1.
3. Reverse the whole array.
Example:
1 2 3 4 5
k = 3
Step 1. Reverse the array elements from 0 to 2: 3 2 1 4 5
Step 2. Reverse the array elements from 3 to 4: 3 2 1 5 4
Step 3. Reverse the whole array: 4 5 1 2 3
Time Complexity: O(n)
Space Complexity: O(1)

What happens if k > n?
Example:
array: 1 2 3 4 5
k = 8
Then after 8 rotations, the array will be:
4 5 1 2 3
which is same as rotating the array 3 times (k%n = 8%5 = 3)
If this is not handled in algorithms 2 (using temporary array) and 3 (using array reversal), we get an ArrayIndexOutOfBoundsException.
So, we add following checks on k in all 3 algorithms:
1. If k < 0, throw IllegalArgumentException
2. If k > n, set k = k%n

Code Snippet

			
package com.ideserve.questions.saurabh;

import java.util.Arrays;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an array and a positive integer k, rotate the array k times.
 * Example: 
 * Array:  1 2 3 4 5
 * k: 3
 * Output: 4 5 1 2 3 
 *
 * @author Saurabh
 */
public class RotateArray {

	// Rotate array by using reversing operation on the array
	// O(n) time, O(1) space
	public static void rotateArrayUsingReverse(int[] array, int k) {
		
		if(k < 0) {
			throw new IllegalArgumentException("k cannot be negative!");
		}
		
		if(array == null || array.length < 2) {
			return;
		}

		int n = array.length;
		if(k > n)
			k = k%n;

		reverseArray(array, 0, k-1);
		reverseArray(array, k, n-1);
		reverseArray(array, 0, n-1);
	}
	
	// Reverse an array between start (s) and end (e)
	private static void reverseArray(int[] array, int s, int e) {
		while(s < e) {
			int tmp = array[s];
			array[s] = array[e];
			array[e] = tmp;
			s++;
			e--;
		}
	}

	// Solution using temporary array 
	// O(n) time, O(k) space
	public static void rotateArrayUsingTmp(int[] array, int k) {
		if(k < 0) {
			throw new IllegalArgumentException("k cannot be negative!");
		}
		
		if(array == null || array.length < 2) {
			return;
		}

		int n = array.length;
		if(k > n)
			k = k%n;

		int[] tmp = new int[k];
		for(int i = 0; i < k; i++) {
			tmp[i] = array[i];
		}
		for(int i = k; i < n; i++) {
			array[i-k] = array[i];
		}
		for(int i = n - k, j = 0; i < n; i++, j++) {
			array[i] = tmp[j];
		}
	}
	
	// Naive Solution - O(n*k)
	// Rotate array by using the method rotateArrayOnce k times
	public static void rotateArrayNaive(int[] array, int k) {
		
		if(k < 0) {
			throw new IllegalArgumentException("k cannot be negative!");
		}
		
		if(array == null || array.length < 2) {
			return;
		}

		int n = array.length;
		if(k > n)
			k = k%n;
		
		for(int i = 0; i < k; i++) {
			rotateArrayOnce(array);
		}		
	}

	// Rotate array 1 element at a time
	public static void rotateArrayOnce(int[] array) {
		int first = array[0];
		for(int i = 0; i < array.length-1; i++) {
			array[i] = array[i+1];
		}
		array[array.length-1] = first;
	}
	
	public static void main(String[] args) {
		testArrayRotationNaive();
		testArrayRotationTmp();
		testArrayRotationReverse();
	}
	
	private static void testArrayRotationNaive() {
		int[] array = {1,2,3,4,5};
		int k = 8;
		System.out.println("Original Array: ");
		System.out.println(Arrays.toString(array));
		rotateArrayNaive(array, k);
		System.out.println("After Rotation " + k + " times using naive algorithm: ");
		System.out.println(Arrays.toString(array));		
	}
	
	private static void testArrayRotationTmp() {
		int[] array = {1,2,3,4,5};
		int k = 8;
		System.out.println("Original Array: ");
		System.out.println(Arrays.toString(array));
		rotateArrayUsingTmp(array, k);
		System.out.println("After Rotation " + k + " times using temporary array: ");
		System.out.println(Arrays.toString(array));		
	}
	
	private static void testArrayRotationReverse() {
		int[] array = {1,2,3,4,5};
		int k = 8;
		System.out.println("Original Array: ");
		System.out.println(Arrays.toString(array));
		rotateArrayUsingReverse(array, k);
		System.out.println("After Rotation " + k + " times using reversal: ");
		System.out.println(Arrays.toString(array));		
	}
}