How to Rotate an Array to Left/Right by a Given Number in Java - Coding Problem

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 a 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 you are asked to rotate the same array twice by right then you'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 seen many programmers struggle 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]

It's also very different from the String rotation problem we have seen earlier, where we had to check if two strings are the rotation of each other or not. Here we are not checking if two arrays are the rotation of each other, but we need to rotate the array itself.






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 like [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 like 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 like 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 the 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:


Java Program to Rotate an Array by Given Number


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.

Btw, If you are ready for Coding Interview then you can also take TripleByte's quiz and go directly to the final round of interviews with top tech companies like Coursera, Adobe, Dropbox, Grammarly, Uber, Quora, Evernote, Twitch etc


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


Other Array and Data Structure Coding Problems you may like
  • 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)
  • 50+ Data Structure and Algorithms Questions from Interviews (questions)
  • How to find the largest and smallest number in an array without sorting? (solution)
  • How to find all pairs in an array whose sum is equal to k (solution)
  • Top 20 String Coding Problems from Interivews (questions)
  • 10 Courses to Learn Data Structure and Algorithms for Interivews (courses)
  • 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)
  • Binary Search Algorithm without Recursion (algorithm)
  • Prime Number Generation Algorithms - Sieve of Eratosthenes (algorithm)
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.


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 for programmers. The list contains a lot of useful online courses to learn algorithms from scratch for both beginners and intermediate programmers.

No comments:

Post a Comment