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)

Answer 2

ArrayUtil class is used to provide following utilities in primitive array

1. swap array elements
2. reverse array between startIndex and endIndex
3. leftRotate array by shift

---

Algorithm for array rotation by shift-

1. If we have to reverse array by shift value then take mod(%) with array length so that shift will become smaller than array length.
2. Reverse array between index 0 and shift-1
3. Reverse array between index shift and length-1.
4. Reverse complete array between index 0 and length-1.

Space Complexity: In-place Algorithm, No extra space needed so O(1).

Time Complexity : Array reversal of size k take O(k/2) i.e swapping k/2 pairs of elements.

Array Reversal time- O(k) for k size array.

Total time in Rotation-

• O(1) ..........for step 1
• O(shift) ......for step 2
• O(n - shift) ...for step 3
• O(n) ...........for step 4

Total Time for array Rotation: O(1) + O(shift) + O(n-shift) + O(n) = O(n)

public class Solution {

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

        ArrayUtil.leftRotate(a, k);

        for (int i : a)
            System.out.println(i);
    }
}

class ArrayUtil {

    public static final boolean checkIndexOutOfRange(int[] array, int index) {
        if (index < 0 || index > array.length)
            return true;
        return false;
    }

    public static final void swap(int[] array, int i, int j) {
        if (checkIndexOutOfRange(array, i) || checkIndexOutOfRange(array, j))
            return;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static final void reverse(int[] array, int startIndex, int endIndex) {
        if (checkIndexOutOfRange(array, startIndex) || checkIndexOutOfRange(array, endIndex))
            return;
        while (startIndex < endIndex) {
            swap(array, startIndex, endIndex);
            startIndex++;
            endIndex--;
        }
    }

    public static final void reverse(int[] array) {
        reverse(array, 0, array.length - 1);
    }

    public static final void leftRotate(int[] array, int shift) {
        int arrayLength = array.length;
        if (shift >= arrayLength)
            shift %= arrayLength;
        reverse(array, 0, shift - 1);
        reverse(array, shift, arrayLength - 1);
        reverse(array);
    }
}