Array Left rotation by k elements using reversal algorithm

In this article we will see how to left rotate an array by k elements using reversal algorithm, it takes constant space space O(1) 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 using reversal algorithm


1) Reverse array from (0 to k-1)
2) Reverse array from (k to n-1)
3) Reverse array from (0 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) {
		reverse(arr, 0, k - 1);
		reverse(arr, k, n - 1);
		reverse(arr, 0, n - 1);
	}

	private 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--;
		}
	}

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

Complete example: Array rotation using reversal algorithm in Java

package com.tb.array;

import java.util.Arrays;

public class ArrayRotationReversalAlgorithm {

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

	private static void rotate(int[] arr, int n, int k) {
		reverse(arr, 0, k - 1);
		reverse(arr, k, n - 1);
		reverse(arr, 0, n - 1);
	}

	private 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--;
		}
	}

	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