java - How to rotate an array?

Question

I have the following problem to test:

Rotate an array of n elements to the right by k steps.

For instance, 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]. How many different ways do you know to solve this problem?

My solution in intermediate array:

With Space is O(n) and time is O(n), I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy().

public void rotate(int[] nums, int k) {
    if (k > nums.length) 
        k = k % nums.length;
 
    int[] result = new int[nums.length];
 
    for (int i = 0; i < k; i++) {
        result[i] = nums[nums.length - k + i];
    }
 
    int j = 0;
    for (int i = k; i < nums.length; i++) {
        result[i] = nums[j];
        j++;
    }
 
    System.arraycopy(result, 0, nums, 0, nums.length);
}

But is there a better way we can do it with bubble rotate (like bubble sort) in O(1) space?

Answer 1

Method 1 - The Reversal Algorithm(Good One):

Algorithm:

rotate(arr[], d, n)

reverse(arr[], l, n);

reverse(arr[], 1, n-d) ;

reverse(arr[], n - d + 1, n);

Let AB are the two parts of the input array where A = arr[0..n-d-1] and B = arr[n-d..n-1]. The idea of the algorithm is:

Reverse all to get (AB) r = BrAr.

Reverse A to get BrA. /* Ar is reverse of A */

Reverse B to get BA. /* Br is reverse of B */

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7

A = [1, 2, 3, 4, 5] and B = [ 6, 7]

Reverse all, we get BrAr = [7, 6, 5, 4, 3, 2, 1]

Reverse A, we get ArB = [7, 6, 1, 2, 3, 4, 5] Reverse B, we get ArBr = [6, 7, 5, 4, 3, 1, 2]

Here is the Code Snippet:

void righttRotate(int arr[], int d, int n)
{
  reverseArray(arr, 0, n-1);
  reverseArray(arr, 0, n-d-1);
  reverseArray(arr, n-d, n-1);
}

void reverseArray(int arr[], int start, int end)
{
  int i;
  int temp;
  while(start < end)
  {
    temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
   }
}

Method 2 - A Juggling Algorithm

Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets.

If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

1. Elements are first moved in first set arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

2. Then in second set. arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

3. Finally in third set. arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Here is the code:

void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  int gcd = gcd(d, n);
  for (i = 0; i < gcd; i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

int gcd(int a,int b)
{
   if(b==0)
     return a;
   else
     return gcd(b, a%b);
}

Time complexity: O(n)

Auxiliary Space: O(1)

Method 3 - Rotate one by one:

righttRotate(arr[], d, n)

start

For i = 0 to i < d

Right rotate all elements of arr[] by one

end

To rotate by one, store arr[n-1] in a temporary variable temp, move arr[1] to arr[2], arr[2] to arr[3] …and finally temp to arr[0]

Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, rotate arr[] by one 2 times. We get [7, 1, 2, 3, 4, 5, 6] after first rotation and [ 6, 7, 1, 2, 3, 4, 5] after second rotation.

Her is Code Snippet:

void leftRotate(int arr[], int d, int n)
{
  int i;
  for (i = 0; i < d; i++)
    leftRotatebyOne(arr, n);
}

void leftRotatebyOne(int arr[], int n)
{
  int i, temp;
  temp = arr[n-n];
  for (i = 0; i < n-1; i++)
     arr[i] = arr[i+1];
  arr[n - 1] = temp;
}

Time complexity: O(n*d)

Auxiliary Space: O(1)