Arrays: Left Rotation: Hackerrank Solution

Array Left Rotation Hackerrank Solution.


Question: 

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.
Arrays: Left Rotation: Hackerrank Solution Arrays: Left Rotation: Hackerrank Solution Reviewed by Jas Arora on May 31, 2020 Rating: 5

No comments:

If you have any doubts please let me know.

Powered by Blogger.