Rotate an array

Tag: Palantir

Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Method 1: using d extra space.

Method 2: rotate by one

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

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

METHOD 3 (A Juggling Algorithm)

Method 4: reverse algorithm

Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1]. The idea of the algorithm is: Reverse A to get ArB. / Ar is reverse of A / Reverse B to get ArBr. / Br is reverse of B / Reverse all to get (ArBr) r = BA.

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7 A = [1, 2] and B = [3, 4, 5, 6, 7] Reverse A, we get ArB = [2, 1, 3, 4, 5, 6, 7] Reverse B, we get ArBr = [2, 1, 7, 6, 5, 4, 3] Reverse all, we get (ArBr)r = [3, 4, 5, 6, 7, 1, 2]

// Java program for reversal algorithm of array rotation
import java.io.*;

class LeftRotate
{
    /* Function to left rotate arr[] of size n by d */
    static void leftRotate(int arr[], int d)
    {
        int n = arr.length;
        rvereseArray(arr, 0, d-1);
        rvereseArray(arr, d, n-1);
        rvereseArray(arr, 0, n-1);
    }

    /*Function to reverse arr[] from index start to end*/
    static void rvereseArray(int arr[], int start, int end)
    {
        int temp;
        while (start < end)
        {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    /*UTILITY FUNCTIONS*/
    /* function to print an array */
    static void printArray(int arr[])
    {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }

    /* Driver program to test above functions */
    public static void main (String[] args)
    {
        int arr[] = {1, 2, 3, 4, 5, 6, 7};
        leftRotate(arr, 2); // Rotate array by 2
        printArray(arr);
    }
}
/*This code is contributed by Devesh Agrawal*/

Palantir version:

https://github.com/DeanWen/leetCodeInterview/blob/master/Interview/Palantir/Shift%20Array%20(In%20Place).java

/*
* Shift an Array k places in O(n) time and O(1) space
    The Idea
    Reverse a to get ar b.
    Reverse b to get ar br .
    Reverse all to get (ar br )r = ba.
    The Code // rotate abcdefgh left three 
    reverse(0, d-1) // cbadefgh 
    reverse(d, n-1) // cbahgfed 
    reverse(0, n-1) // defghabc 
*/

public static void shiftKthInArray(char[] array, int k) {
    if (array == null || array.length == 0 || k %= array.length == 0) {
        return;
    }
    if (k > array.length) {
        k = k % array.length;
    }

    reverse(array, 0, array.length - 1);
    reverse(array, 0 , k -1);
    reverse(array, k, array.length - 1);
}

public static void reverse(char[] array, int start, int end){    
     int mid =     start + (end - start) / 2;
     for (int i = start; i <= mid; i++) {
         char temp = array[i];
         array[i] = array[end - (i - start)];
         array[end - (i - start)] = temp;
     }
}