Java - Rotating array

In case you don't want to reinvent the wheel (maybe it's an exercise but it can be good to know), you can use Collections.rotate.

Be aware that it requires an array of objects, not primitive data type (otherwise you'll swap arrays themselves in the list).

Integer[] arr = {0,1,2,3,4};
Collections.rotate(Arrays.asList(arr), 2);
System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2]

Arraycopy is an expensive operation, both time and memory wise. Following would be an efficient way to rotate array without using extra space (unlike the accepted answer where a new array is created of the same size).

public void rotate(int[] nums, int k) { // k = 2
    k %= nums.length;
    // {0,1,2,3,4}

    reverse(nums, 0, nums.length - 1); // Reverse the whole Array
    // {4,3,2,1,0}

    reverse(nums, 0, k - 1); // Reverse first part (4,3 -> 3,4)
    // {3,4,2,1,0}

    reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2)
    // {3,4,0,1,2}
}

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--;
    }
}

Another way is copying with System.arraycopy.

    int[] temp = new int[array.length];
    System.arraycopy(array, 0, temp, a, array.length - a);
    System.arraycopy(array, array.length-a, temp, 0, a);

I think the fastest way would be using System.arrayCopy() which is native method:

int[] tmp = new int[a];
System.arraycopy(array, array.length - a, tmp, 0, a);
System.arraycopy(array, 0, array, a, array.length - a);
System.arraycopy(tmp, 0, array, 0, a);

It also reuses existing array. It may be beneficial in some cases. And the last benefit is the temporary array size is less than original array. So you can reduce memory usage when a is small.

Time Complexity = O(n)

Space Complexity = O(1)

The algorithm starts with the first element of the array (newValue) and places it at its position after the rotation (newIndex). The element that was at the newIndex becomes oldValue. After that, oldValue and newValue are swapped.

This procedure repeats length times.

The algorithm basically bounces around the array placing each element at its new position.

unsigned int computeIndex(unsigned int len, unsigned int oldIndex, unsigned int times) {
    unsigned int rot = times % len;
    unsigned int forward = len - rot;

    // return (oldIndex + rot) % len; // rotating to the right
    return (oldIndex + forward) % len; // rotating to the left
}

void fastArrayRotation(unsigned short *arr, unsigned int len, unsigned int rotation) {
    unsigned int times = rotation % len, oldIndex, newIndex, length = len;
    unsigned int setIndex = 0;
    unsigned short newValue, oldValue, tmp;

    if (times == 0) {
        return;
    }

    while (length > 0) {
        oldIndex = setIndex;
        newValue = arr[oldIndex];
        while (1) {
            newIndex = computeIndex(len, oldIndex, times);
            oldValue = arr[newIndex];
            arr[newIndex] = newValue;

            length--;

            if (newIndex == setIndex) { // if the set has ended (loop detected)
                break;
            }

            tmp = newValue;
            newValue = oldValue;
            oldValue = tmp;

            oldIndex = newIndex;
        }
        setIndex++;
    }
}

int[] rotate(int[] array, int r) {
    final int[] out = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        out[i] = (i < r - 1) ? array[(i + r) % array.length] : array[(i + r) % array.length];
    }
    return out;
}

The following rotate method will behave exactly the same as the rotate method from the Collections class used in combination with the subList method from the List interface, i.e. rotate (n, fromIndex, toIndex, dist) where n is an array of ints will give the same result as Collections.rotate (Arrays.asList (n).subList (fromIndex, toIndex), dist) where n is an array of Integers.

First create a swap method:

public static void swap (int[] n, int i, int j){

   int tmp = n[i];
   n[i] = n[j];
   n[j] = tmp;
}

Then create the rotate method:

public static void rotate (int[] n, int fromIndex, int toIndex, 
int dist){

   if(fromIndex > toIndex)

      throw new IllegalArgumentException ("fromIndex (" + 
         fromIndex + ") > toIndex (" + toIndex + ")");

   if (fromIndex < toIndex){

      int region = toIndex - fromIndex;
      int index;

      for (int i = 0; i < dist % region + ((dist < 0) ? region : 0); 
              i++){

         index = toIndex - 1;
     
         while (index > fromIndex)

            swap (n, index, --index);
       }
   }
}

Java solution wrapped in a method:

public static int[] rotate(final int[] array, final int rIndex) {
    if (array == null || array.length <= 1) {
        return new int[0];
    }

    final int[] result = new int[array.length];
    final int arrayLength = array.length;

    for (int i = 0; i < arrayLength; i++) {
        int nIndex = (i + rIndex) % arrayLength;
        result[nIndex] = array[i];
    }
    return result;
}

For Left Rotate its very simple

Take the difference between length of the array and number of position to shift.

For Example

int k = 2;
int n = 5;

int diff = n - k;

int[] array = {1, 2, 3, 4, 5};
int[] result = new int[array.length];
System.arraycopy(array, 0, result, diff, k);
System.arraycopy(array, k, result, 0, diff);

// print the output

Question : https://www.hackerrank.com/challenges/ctci-array-left-rotation
Solution : This is how I tried arrayLeftRotation method with complexity o(n)

• looping once from k index to (length-1 )

• 2nd time for 0 to kth index

  public static int[] arrayLeftRotation(int[] a, int n, int k) {
  int[] resultArray = new int[n];
  int arrayIndex = 0;
  //first n-k indexes will be populated in this loop
  for(int i = k ; i resultArray[arrayIndex] = a[i];
  arrayIndex++;
  }
  // 2nd k indexes will be populated in this loop
  for(int j=arrayIndex ; j<(arrayIndex+k); j++){
  resultArray[j]=a[j-(n-k)];
  }
  return resultArray;
  }

package com.array.orderstatistics;

import java.util.Scanner;

public class ArrayRotation {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int r = scan.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();

        if (r % n == 0) {
            printOriginalArray(a);
        } else {
            r = r % n;
            for (int i = 0; i < n; i++) {
                b[i] = a[(i + r) < n ? (i + r) : ((i + r) - n)];
                System.out.print(b[i] + " ");
            }
        }
    }

    private static void printOriginalArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

Following routine rotates an array in java:

public static int[] rotateArray(int[] array, int k){
    int to_move = k % array.length;
    if(to_move == 0)
      return array;
    for(int i=0; i< to_move; i++){
      int temp = array[array.length-1];
      int j=array.length-1;
      while(j > 0){
        array[j] = array[--j];
      }
      array[0] = temp;
    }
    return array;
 }

You can do something like below

class Solution {
    public void rotate(int[] nums, int k) {
        if (k==0) return;
        if (nums == null || nums.length == 0) return;

        for(int i=0;i<k;i++){
            int j=nums.length-1;
            int temp = nums[j];
            for(;j>0;j--){
                nums[j] = nums[j-1];
            }
            nums[0] = temp;
        }
    }
}

In the above solution, k is the number of times you want your array to rotate from left to right.

Question : Rotate array given a specific distance . Method 1 : Turn the int array to ArrayList. Then use Collections.rotate(list,distance).

class test1 {
    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 4, 5, 6 };

        List<Integer> list = Arrays.stream(a).boxed().collect(Collectors.toList());

        Collections.rotate(list, 3);
        System.out.println(list);//[4, 5, 6, 1, 2, 3]

    }// main
}

I use this, just loop it a times

public void rotate(int[] arr) {
    int temp = arr[arr.length - 1];

    for(int i = arr.length - 1; i > 0; i--) {
        arr[i] = arr[i - 1];
    }

    arr[0] = temp;
}