Array Left rotation by k elements using extra space

In this article we will see how to left rotate an array by k elements using extra space O(k) and in O(n) time complexity, lets assume the given array is:

Input: int [] arr = {1,2,3,4,5,6,7};

k=3

Output: int [] arr = {4,5,6,7,1,2,3};

Algorithm: Array rotation

1) Store k element from left to a new array of size k.
2) Shift remaining elements in original array to the left by i-k.
3) Copy temp array elements to the end of original array from n-k to n-1.

k=number of elements to be rotated, i=current element index, n=length of array


	private static void rotate(int[] arr, int n, int k) {
		int[] tmp = new int[k];

		// copy k elements to a temp array
		for (int i = 0; i < k; i++)
			tmp[i] = arr[i];

		// shift remaining elements by 3 to the left
		for (int i = k; i < n; i++)
			arr[i - k] = arr[i];

		// copy elements in temp to the end of original array from n-k to n-1
		for (int i = 0; i < tmp.length; i++)
			arr[n - k + i] = tmp[i];

	}

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


Complete example - Array rotation in Java


package com.tb.array;

import java.util.Arrays;

public class RotateArrayLeftUsingExtraSpcace {

	private static int[] arr = { 1, 2, 3, 4, 5, 6, 7 };

	private static void rotate(int[] arr, int n, int k) {
		int[] tmp = new int[k];

		// copy k elements to a temp array
		for (int i = 0; i < k; i++)
			tmp[i] = arr[i];

		// shift remaining elements by 3 to the left
		for (int i = k; i < n; i++)
			arr[i - k] = arr[i];

		// copy elements in temp to the end of original array from n-k to n-1
		for (int i = 0; i < tmp.length; i++)
			arr[n - k + i] = tmp[i];

	}

	public static void main(String[] args) {
		print(arr);

		// rotate by 3
		rotate(arr, arr.length, 3);

		print(arr);
	}

	private static void print(int[] arr) {
		System.out.println();
		Arrays.stream(arr).forEach(System.out::print);
	}
}

Output: Output of above example will look something like this.

1234567 4567123