Thursday, April 20, 2023

How to Rotate Array to Left or Right in Java? Example - LeetCode Solution

Hello guys, rotating an array in Java is a common coding problems which are often used to teach beginners coding as well used during interviews to check candidate's programming and data structure skills. This problem may look easy but its not that easy, especially if you are not coding regular. In order to rotate an array of n elements to the right by kth index, you need to rearrange the item in such a way that the array will start from k + 1the element.  For example, with n = 7 and k = 3, the array [1, 2, 3, 4 ,5, 6, 7] is rotated to [5, 6, 7, 1, 2, 3, 4]. See, it looks like you pick the the 4th element and rotated the array in right direction. The problem becomes even more interesting when interviewer ask you to rotate the array by left or right and in place. Could you do it in-place with O(1) extra space?

If you are still confused with what is array rotation actually means then don't confuse, just think as shifting elements. For example, if you have rotate the array by left with first element then fist element will move to the last and second element will become the first element. 

Similarly, if you have to rotate an array by right then last element will come to the first place and the second last element will become the first element. It's that simple. 





Java Solution to Rotate an Array in Java

This is the problem of rotating array on right and the simplest solution which comes in my mind is to use a new array of same size and copy the element from old array
import java.util.Arrays;


/**
 * Java Program to rotate array in Java
 * Problem : Rotate an integer array of n elements after kth index.
 * For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] 
 * is rotated to [5,6,7,1,2,3,4]
 * 
 * @author Javin Paul
 */

public class RotateArray {

    public static void main(String args[]) {
        int[] input = {1, 2, 3, 4, 5, 6, 7};
        System.out.println(Arrays.toString(input));
        System.out.println(Arrays.toString(rotate(input, 3)));
        
        int[] sample = {1, 2, 3, 4, 5, 6, 7};
        rotateInPlace(sample, 3);
        System.out.println(Arrays.toString(sample));
    }

    /*
     * rotates array by copying contents into a new array
     * time complexity O(n) and need additional space of O(n)
     * Can you do better? think do you really need a temporary
     * array or same size?
     */
    public static int[] rotate(int[] nums, int k) {
        
        int[] rotated = new int[nums.length];
        
        // copying the rotated portion
        for(int i= k + 1, j=0;  i<nums.length; i++, j++){
            rotated[j] = nums[i];
        }
        
        // copying the not rotated portion
        for(int i=0, j=rotated.length -1 - k; i<=k; i++, j++){
            rotated[j] = nums[i];
        }
        
        return rotated;
    }
    
    /**
     * Classical approach of rotating array in place, based upon
     * a technique demonstrated on Programming Pearls, a must
     * read book for any programmer.
     * In this solution, we write a method to rotate an array
     * between two indexes and then call this method thrice
     * on the array we want to rotate as follows :
     * reverse(array, 0, k-1)  //reverse unrotated part
     * reverse(array, k, length -1) // reverse rotated part
     * reverse(array, 0, length -1) // reverse whole array
     */
    public static void rotateInPlace(int[] input, int index){
        reverse(input, 0, index);
        reverse(input, index+1, input.length - 1);
        reverse(input, 0, input.length -1);
    }
    
    public static void reverse(int[] input, int startIdx, int endIdx){
        int length = startIdx + endIdx;
        for(int i=startIdx, j=endIdx; i<=length/2; i++, j--){
            int temp = input[j];
            input[j] = input[i];
            input[i] = temp;
        }
    }

}

JUnit Test case for Array Rotation Problem

Here is our unit test to check if array is properly rotated or not. Whether its interview or day to day coding, you should practice writing test before coding. This is known as Test driven development and its often result in better quality code. 


import org.junit.Test;
import static org.junit.Assert.*;

/**
 * Java Program to test our method to rotate array in Java around an index.
 *  
 * @author WINDOWS 8
 *
 */
public class PrimeNumberGeneratorTest{
    
   @Test
   public void testRotateArray(){
       int[] first = {1, 2, 3, 4, 5};
       assertArrayEquals(new int[]{2,3,4,5,1}, RotateArray.rotate(first, 0));
       assertArrayEquals(new int[]{3,4,5,1,2}, RotateArray.rotate(first, 1));
       assertArrayEquals(new int[]{4,5,1,2,3}, RotateArray.rotate(first, 2));
       assertArrayEquals(new int[]{5,1,2,3,4}, RotateArray.rotate(first, 3)); 
   }
   
   @Test
   public void testRotateArrayInPlace(){
       int[] first = {1, 2, 3, 4, 5};
       RotateArray.rotateInPlace(first, 0);
       assertArrayEquals(new int[]{2,3,4,5,1}, first);
       
       int[] second = {1, 2, 3, 4, 5};
       RotateArray.rotateInPlace(second, 1);
       assertArrayEquals(new int[]{3,4,5,1,2}, second);
       
       int[] third = {1, 2, 3, 4, 5};
       RotateArray.rotateInPlace(third, 2);
       assertArrayEquals(new int[]{4,5,1,2,3}, third);
       
       int[] fourth = {1, 2, 3, 4, 5};
       RotateArray.rotateInPlace(fourth, 3);
       assertArrayEquals(new int[]{5,1,2,3,4}, fourth); 
   }
   
   @Test
   public void testReverseArrayBetweenGivenIndex(){
       int[] input = {1, 2, 3, 4};
       RotateArray.reverse(input, 0, input.length -1);
       assertArrayEquals(new int[]{4, 3, 2, 1}, input);
       
       int[] second = {1, 2, 3, 4};
       RotateArray.reverse(second, 0, 1);
       assertArrayEquals(new int[]{2, 1, 3, 4}, second);
       
       int[] third = {1, 2, 3, 4};
       RotateArray.reverse(third, 1, 2);
       assertArrayEquals(new int[]{1, 3, 2, 4}, third);
       
       int[] fourth = {1, 2, 3, 4};
       RotateArray.reverse(fourth, 2, 3);
       assertArrayEquals(new int[]{1, 2, 4, 3}, fourth);
       
   }
}

That's all about how to rotate array in Java. We have seen couple of ways to rotate array in Java. you can rotate array either on left or right side given to any pivot.

Other Array and Coding Problems you may like
  • How to check if an array contains a particular value? (solution)
  • Prime Number Generation Algorithms - Sieve of Eratosthenes (algorithm)
  • How to remove an element from an array in Java? (solution)
  • How to sort an array in place in Java? (solution)
  • Top 5 Websites for Coding Interview Preparation (websites)
  • 7 Best Courses to learn Data Structure and Algorithms? (courses)
  • How to find one missing number in a sorted array? (solution)
  • 10 Courses to Learn Data Structure and Algorithms for Interviews (courses)
  • How to find the largest and smallest number in an array without sorting? (solution)
  • Top 20 String Coding Problems from Interviews (questions)
  • How to find duplicates from an unsorted array in Java? (solution)
  • How to remove duplicates from an array in Java? (solution)
  • 75 Programming Questions to Crack Any Coding Interview (list)
  • Binary Search Algorithm without Recursion (algorithm)
  • How to find all pairs in an array whose sum is equal to k (solution)
  • 20+ Array-Based Coding Problems from interviews (questions)
Thanks for reading this article so far. If you like this array-based coding interview question and my solution and explanation then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. - If you want to level up your DSA skills and looking to learn Data Structure and Algorithms from scratch or want to fill gaps in your understanding and looking for some free courses, then you can check out this list of Free DSA and Algorithms Courses to start with.

No comments :

Post a Comment