How to Rotate an Array to Left and Right by Given Number in Java?

Hello guys, welcome to this post with another array based coding problem. In the last article, we've learned about finding missing numbers in the array with duplicates and today we'll solve the problem of rotating an array by left or right by given number. For example, suppose an integer array {1, 2, 3} is given and it was asked to rate this array to the left by 3 then the result array will look like {2, 3, 1} because it was rotated twice on left. Similarly if asked to rotate the same array twice by right then we'll get {1, 2, 3}, the same array is back. This is an interesting problem and it's quite easy to solve but I have many programmers struggles with this one as well. So, a little bit of practice and learning will not hurt.

Problem:

Suppose, you were given an integer array [1, 2, 3, 4, 5, 6, 7, 8] and asked to rotate left by 4 and then rotate right by 4. Write a program to accomplish array rotation by left and right.

input: [1, 2, 3, 4, 5, 6, 7, 8]

first output: [5, 6, 7, 8, 1, 2, 3, 4]
second output: [1, 2, 3, 4, 5, 6, 7, 8]


Solution:

The solution to this problem is simple, but you need what is the meaning of rotating an array to left and right. For that sake let's take an example of an integer array with three elements e.g. [10, 20, 30].

If we rotate this to left by 1 then every element will move towards the start of the array (index zero) by 1 place and in this course the first element, 10 will be moved from the first index to the last index. The rotate array will now look like [20, 30, 10].

Similarly, to rotate an array by right, we need to shift all elements towards the end of the array, which means the last element will end up with the first position.

For example, if take [20, 30, 10] and rotate this array to right by 1 place it will look like [10, 20, 30], which is same as the original array.

Btw, if you are not familiar with array and other essential data structure e.g. list, binary tree, stack, queue etc, Please refer Data Structures and Algorithms: Deep Dive Using Java, an excellent course to master essential data structure.

How to Rotate an Array Left and Right by Given Number?



Code:

Here is the sample Java program to rotate arrays in Java. We have created two methods here rotateLeft() and rotateRight(), both method takes array and numberOfRotations as a parameter.

Even though I have added length to capture the length of input array it's optional because you can always get that from the array as well.

The rotateLeft() method loop over the array and shift each element towards the first index i.e. towards left.

Since the first element will be lost by this, we store it into a temporary variable before start with shifting. Later we put that element at the end of the array. The same process is repeated as many times required by numberOfRoatation.

The rotateRight() method is very similar to rotateLeft() method with the only difference that here elements are moved towards last index i.e. towards the right.

The last element is stored in a temporary variable and later put back into the first position, which completes the rotation.

Here is the complete Java program:

package tool;

import java.util.Arrays;

/**
 * 
 * A simple Java Program to rotate an array by left and right by given number.
 */
public class Hello {

  public static void main(String[] args) {
    int[] input = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int k = 4;

    System.out.println("Rotate given array " + Arrays.toString(input)
        + " by 4 places to the left.");

    int[] rotatedArray = rotateLeft(input, input.length, k);

    System.out.println("Rotated array: " + Arrays.toString(rotatedArray));

    System.out.println("Rotate given array " + Arrays.toString(input)
        + " by 4 places to the right.");

    rotatedArray = rotateRight(rotatedArray, rotatedArray.length, k);

    System.out.println("Rotated array: " + Arrays.toString(rotatedArray));

  }

  /**
   * Java method to rotate a given array to the left specified by numOfRotations
   * times
   * 
   * @param input
   * @param length
   * @param numOfRotations
   * @return rotated array
   */
  private static int[] rotateLeft(int[] input, int length, int numOfRotations) {
    for (int i = 0; i < numOfRotations; i++) {

      // take out the first element
      int temp = input[0];
      for (int j = 0; j < length - 1; j++) {

        // shift array elements towards left by 1 place
        input[j] = input[j + 1];
      }
      input[length - 1] = temp;
    }
    return input;

  }

  /**
   * Java method to rotate a given array to the right specified by
   * numOfRotations times
   * 
   * @param input
   * @param length
   * @param numOfRotations
   * @return rotated array
   */
  private static int[] rotateRight(int[] input, int length, int numOfRotations) {
    for (int i = 0; i < numOfRotations; i++) {

      // take out the last element
      int temp = input[length - 1];
      for (int j = length - 1; j > 0; j--) {

        // shift array elements towards right by one place
        input[j] = input[j - 1];
      }
      input[0] = temp;
    }
    return input;

  }

}

Output
Rotate given array [1, 2, 3, 4, 5, 6, 7, 8] by 4 places to the left.
Rotated array: [5, 6, 7, 8, 1, 2, 3, 4]
Rotate given array [5, 6, 7, 8, 1, 2, 3, 4] by 4 places to the right.
Rotated array: [1, 2, 3, 4, 5, 6, 7, 8]


Analysis:

The time complexity of this solution is O(n*k) where n is the number of elements in the array and k is the number of rotation.

If k=n then the solution will be of O(n^2). This is because in each rotation we shift all array elements and we need to repeat rotation k times.

The space complexity of this solution is O(1) because we have not used any additional array. The space allocated for a temporary variable is not counted.

If you are not confident in calculating time and space complexity of the algorithm, I suggest you join a good data structure and algorithm course like  Algorithms and Data Structures in depth, which covers algorithm complexity in depth.


That's all about how to rotate a given array to left and right by given number in Java. This is a simple but interesting array based coding interview question which you will often find in software engineering interviews. The key to solving this problem is knowing what does array rotation means and how to rotate an array of left and right which is nothing but shifting elements towards the start and end position.


Other Array-based Coding Problems you may like
  • How to find the largest and smallest number in an array without sorting? (solution)
  • How to check if an array contains a particular value? (solution)
  • How to remove an element from an array in Java? (solution)
  • How to find one missing number in a sorted array? (solution)
  • How to find all pairs in an array whose sum is equal to k (solution)
  • How to find duplicates from an unsorted array in Java? (solution)
  • How to remove duplicates from an array in Java? (solution)
  • How to sort an array in place in Java? (solution)
  • 75 Programming Questions to Crack Any Coding Interview (list)

Thanks for reading this article so far. If you like this array based coding interview question and my solution and explanation then please share with your friends and colleagues. If you have any questions or feedback then please drop a note.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz
Cracking the Coding Interview - 189 Questions and Solutions

P.S. If you are looking for some free resources, then you can also check out this list of free data structure and algorithm courses.


No comments:

Post a Comment