Arrays: Left Rotation: Hackerrank Solution

Question: 

A left rotation operation on an array shifts each of the array's elements  unit to the left. For example, if  left rotations are performed on array , then the array would become .

Given an array  of  integers and a number, , perform  left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

Function Description

Complete the function rotLeft in the editor below. It should return the resulting array of integers.

rotLeft has the following parameter(s):

• An array of integers .
• An integer , the number of rotations.

Input Format

The first line contains two space-separated integers  and , the size of  and the number of left rotations you must perform.

The second line contains  space-separated integers .

Output Format

Print a single line of  space-separated integers denoting the final state of the array after performing  left rotations.

Sample Input

5  4

1  2  3  4  5

Sample Output

5 1 2  3  4

Solution:

The solution is pretty simple there are two ways to solve it.

First method: Simply shift values again and again from A[n] to A[n-1] to visualise better, let's take the above example and do it step by step.  

• A = [ 1 , 2, 3, 4, 5] , K = 4
• After 1st rotation the values will shift and array looks like A = [ 2, 3, 4, 5, 1]
• After 2nd rotation the values in the array will be A = [3, 4, 5, 1, 2]
• After 3rd rotation the value in the array will be A = [4, 5, 1, 2, 3]
• After 4th rotation the value in the array will be A = [5, 4, 1, 2, 3]

This method is a little slow but is acceptable in the platform.

The time complexity of the solution is O(n^2).

The code is shared below.

static int[] rotLeft(int[] arr, int numOfRotation) {

   int i = 0, key = 0;

   int size = arr.length;

   while(numOfRotation > 0){

    key = arr[0];

    for(i = 1;i < n; i++)

      arr[i-1] = arr[i]; //Shifting values here

    arr[n-1] = key;

    numOfRotation--;

    }

  return arr;

  }

Second Method:

This method is a little tricky and you will have to think of corner cases beforehand to apply this method.

The steps are 

• Check if the numOfRotation does not exceed the size we do this by using mod (%) operator.
• Reverse the entire array.
• Reverse the array up to the index (a.length - k - 1).
• Reverse the remaining half of the array, i.e. (a.length - k To a.length) 

Tip: Because we are using reverse function again and again it's always a good practice to create reusable functions.

The time complexity of the code is O(n).

The code is given below. 

static int[] rotLeft(int[] arr , int numOfRotation) {

    numOfRotation %= arr.length; // managing the edge cases if K > size

    if(numOfRotation <= 0) return arr;

    int n = arr.length;

    reverse(arr, 0, n-1);

    reverse(arr, 0, n - numOfRotation - 1);

    reverse(arr, n - numOfRotation, n-1);

    return arr;

  }

  static void reverse(int[] arr, int left, int right){

    int temp = 0;

    while(left <= right){

      temp = arr[left];

      arr[left] = arr[right];

      arr[right] = temp;

      left++;

      right--;

    }

  }

Thanks for reading, hope it helps.