The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Rotating an array, right, is the same as rotating the array clockwise. Three ways of rotating the array, right, will be explained in this tutorial, beginning with rotating the array one-by-one.

Consider the following array:

    [0, 1, 2, 3, 4, 5, 6, 7]  

If the array is rotated right by 3 places, then the array would become:

    [5, 6, 7, 0, 1, 2, 3, 4]  

Rotation in the array is defined as the process of rearranging the elements in the array by shifting each element to a new position, by same distance. The elements towards the end, cycle to the front of the array.

The letter, d can be used as the number of shifts. d can be 0; it can be 1; it can be 2; it can be 3; it can be 4; etc.

Rotate Right, One-by-One

This is the brute-force (naive) approach.

Task

Rotate the following array, right by d=3 positions:

    [0, 1, 2, 3, 4, 5, 6, 7] 

Do it in a time complexity of O(n x d) and a space complexity of O(n), where n is the size (length) of the array and d is the number of rotating positions.

Illustration

The given array is:

    [0, 1, 2, 3, 4, 5, 6, 7]

For the first position shift, the array becomes:

    [7, 0, 1, 2, 3, 4, 5, 6]

For the second position shift, the array becomes:

    [6, 7, 0, 1, 2, 3, 4, 5]

For the third position shift, the array becomes:

    [5, 6, 7, 0, 1, 2, 3, 4]

The following program does the rotation with d=3 (read through the code and comments):

public class Program
{
    public static void rightRotateArr(int []arr, int d) { 
        int n = arr.Length;
    
        // Repeat the rotation d times
        for (int i = 0; i < d; i++) {
            // Right rotate the array by one position
            int last = arr[n - 1];
            for (int j = n - 1; j > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[0] = last;      
        }
    }

    public static void Main(string[] args)
    {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};
        int d = 3;

        rightRotateArr(arr, d);
  
        for (int i = 0; i < arr.Length; i++) 
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
}

The outer for-loop does 3 iterations corresponding to d=3. At the beginning of the outer for-loop, the last element of the array is first recorded. The inner for-loop then shifts each element up by one place. The last element is then put in the position of the first element, at the bottom of the outer for-loop, outside the inner for-loop (but inside the outer for-loop). This process is repeated 3 times for d=3.

The output is:

    5 6 7 0 1 2 3 4 

as expected.

Rotate Right Using Temporary Array

This approach uses a temporary array of size n, where n is the length of the original array. If the array is rotated right by d positions, the last d elements will be in the beginning of the array, and the first (n - d) elements will take the rest of the array to the end, in order.

Algorithm Summary

- Copy the last d elements of the original array into the first d positions of the temporary array.
- Then copy the first n - d elements of the original array to the right part of the temporary array.
- Finally, copy all the elements of temporary array back into the original array.

Task

Repeat the above problem for a time complexity of O(n) and space complexity of O(n), using temporary array.

The following program does the rotation with d=3 (read through the code and comments):

public class Program
{
    public static void rotateArr(int []arr, int d) { 
        int n = arr.Length;
    
        // Handle case when d > n
        d %= n;    //modulus
  
        // To store rotated version of array
        int[] temp = new int[n];

        // Copy last d elements to the front of temp
        for (int i = 0; i < d; i++)
            temp[i] = arr[n - d + i];

        // Copy the first n - d elements to the back of temp
        for (int i = 0; i < n - d; i++)
            temp[i + d] = arr[i];

        // Copy the elements of temp in arr to get the 
        // final rotated array
        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }

    public static void Main(string[] args)
    {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};
        int d = 3;

        rotateArr(arr, d);
  
        for (int i = 0; i < arr.Length; i++) 
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
}

The output is:

    5 6 7 0 1 2 3 4 

as expected.

The time complexity is O(n) as the first two for-loops compliment one another. The space complexity is actually O(2n), but the coefficient (multiplier of 2) is omitted when quoting complexity.

Rotate Right Using Reversal Algorithm

This approach is based on the observation that if the array is rotated right by d positions, the last d elements will be in the front and the first (n - d) elements will be in the right part, to the end of the array.

Algorithm Summary

- First reverse all the elements of the array.
- Then reorder the first d elements by reversing them.
- Finally, reorder the rest of the (n - d) elements, by reversing them, to get the complete rotated array.

Task

Repeat the above problem for a time complexity of O(n) and space complexity of O(n), using Reversal Algorithm.

The following program does the rotation with d=3 (read through the code and comments):

public class Program
{
    // Function to reverse a portion of the array from start to end
    public static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];    //temporary variable of O(1) space
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    public static void rotateArr(int []arr, int d) { 
        int n = arr.Length;
    
        // Handle the case where d > size of array
        d %= n;

        // Reverse the entire array
        reverse(arr, 0, n - 1);

        // Reverse the first d elements
        reverse(arr, 0, d - 1);

        // Reverse the remaining n-d elements
        reverse(arr, d, n - 1);
    }

    public static void Main(string[] args)
    {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7};
        int d = 3;

        rotateArr(arr, d);
  
        for (int i = 0; i < arr.Length; i++) 
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
}

The output is:

    5 6 7 0 1 2 3 4 

as expected.

The time complexity is actually O(2n) for the overall two reversals, but the coefficient (multiplier of 2) is omitted when quoting complexity. The space complexity is O(n). The helper function reverse(), used a space of O(1), which is ignored.

What Approach to choose

Choose the approach with the least actual time complexity or least actual space complexity, or both. The Rotate Right, One-by-One is definitely not the approach to choose, because of its high time complexity of O(n x d).

Left (Counter Clockwise) Rotation

This is left as exercises for the reader. The reader should repeat all the above 3 exercises for left rotation.

Thanks for reading.