[Hackerrank] – Left Rotation Solution

Question: You are given an array of integers. After a left rotation of k times, find the resultant array.

Example 1:
Input: arr [ ] = {1, 2, 3, 4, 5}, size = 5, k = 2
Output: {3, 4, 5, 1, 2}

Example 2:
Input: arr [ ] = {4, 8, 15, 16, 23, 42}, size = 6, k = 12
Output: {4, 8, 15, 16, 23, 42}

Terminology:

To understand rotation of an array, you can assume that the array is kind of on an infinite conveyor belt, that keeps on looping. So if you perform left rotation, every element would shift one step to the left. Since the element at 0th position cannot go anywhere, it loops back and moves to the last position.

Problem Statement:

I want to simplify the problem statement before we start to solve it.

You are given an array of integers, and you are required to perform left rotation on it k number of times. You then need to return the resultant array.

      ----+---+---+---+----
arr = | 1 | 2 | 3 | 4 | 5 |
      ----+---+---+---+----
size = 5
k = 2

// After 1 rotation
      ----+---+---+---+----
arr = | 2 | 3 | 4 | 5 | 1 |
      ----+---+---+---+----
// After 2 rotations
      ----+---+---+---+----
arr = | 3 | 4 | 5 | 1 | 2 |     <---- Answer
      ----+---+---+---+----Code language: plaintext (plaintext)

It could be possible that the value of k is more than the size of the array. Note that even if the value of k is greater than the size of the array, you can still rotate the array. If the size of array is 5, after 5 rotations, the array would look exactly the same. A 6th rotation is basically equivalent to 1st rotation.

Brute Force Method:

This is one of the favorite problem of interviewers as it can be solved in many different ways. It helps the interviewer to understand your problem solving skills. But before looking at any efficient ways to solve the problem, let us look at the Brute Force solution.

It would look something like:

1. Store the 0th element of the array in a temporary variable.
2. Shift all the elements one by one one position to the left.
3. Put the 0th element stored in the temporary variable at the last position in the array.
4. This completes 1 rotation of the array.
5. Repeat steps 1-4 for k times.

Upon performing these steps, you will eventually reach the answer. But it would take up a lot of time if the array size is huge and the number of rotations are also high. Hence, this approach would not be feasible for huge input sets.

Method 1: (Optimized Brute Force)

Instead of rotating the array one step at a time, we can rotate the array in complete chunks. First of all, we need to understand that if the array size is 5, and the value of k is 7, then it is equivalent to:

Resultant\ rotations => 7 \bmod 5 = 2
\newline
OR
\newline
Resultant\ Rotations = k \bmod size

Now, we know what is the effective number of rotations we need to perform. So instead of rotating the array one by one, we can do it in a complete chunk.

1. Store the first k elements of the array in a temp array.
2. Shift each element of the rest of the array k places to the left.
3. Store the elements of the temp array back in the original array at the very end.

Performing these 3 steps would give you your answer. You can see that we cleverly optimized the brute force approach to solve this problem.

Code:

  public void rotateLeft(int[] arr, int k) {
    k %= arr.length;
    int[] temp = new int[k];

    // Store the first k elements in a temp array
    for (int i = 0; i < temp.length; i++) {
      temp[i] = arr[i];
    }

    // Shift rest of the arr[]
    for (int i = 0; i < arr.length - k; i++) {
      arr[i] = arr[i + k];
    }

    // Store back the k elements
    for (int i = arr.length - k; i < arr.length; i++) {
      arr[i] = temp[i - k - 1];
    }
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(k)

Method 2: Using auxiliary reverse method

This method is a bit tricky and it involves some math magic. Let us assume that you have a function to reverse an array, that takes in a start index, and an end index. As a result, it would reverse the elements between those indexes. Once you have determined the effective number of rotations required, the algorithm would look something like:

1. First of all reverse all the numbers in the array.
2. Reverse the first (size - k) numbers.
3. Reverse the last k numbers.

This technique will give you the answer and it may not seem very obvious at once. If you brain storm a little, and try to write down a few sample test cases yourself by performing left rotation, then probably you can come up with the solution on your own.

Code:

  // Helper function to reverse an array from start index to end index
  public void reverse(int[] nums, int start, int end) {
    while (start < end) {
      int temp = nums[start];
      nums[start] = nums[end];
      nums[end] = temp;
      start++;
      end--;
    }
  }

  public void rotateLeftUsingReverse(int[] arr, int k) {
    k %= arr.length;

    // Reverse all numbers
    reverse(arr, 0, arr.length - 1);

    // Reverse first arr.length-k numbers
    reverse(arr, 0, arr.length - k - 1);

    // Reverse last k numbers
    reverse(arr, arr.length - k, arr.length - 1);
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

Check out the problem on HackerRank.
You can also find the code and test cases on Github.

Video Explanation: