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):

// C Program to right rotate the array by d positions
// by rotating one element at a time

#include <stdio.h>

// Function to right rotate array by d positions
void rightRotateArr(int arr[], int n, int d) {

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

int main(int argc, char **argv)
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7};
    int d = 3;
    int n = sizeof(arr) / sizeof(arr[0]);    //divide size of array by size of one (first) element

    rightRotateArr(arr, n, d);
  
    for (int i = 0; i < n; i++) 
        printf("%i ", arr[i]);
    printf("\n");
    
    return 0;
}

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):

// C Program to right rotate the array by d positions
// using temporary array

#include <stdio.h>

// Function to rotate array by d positions using a temporary array
void rotateArr(int arr[], int n, int d) {
    
    // Handle case when d > n
    d %= n;    //modulus
  
    // To store rotated version of array
    int temp[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];
}

int main(int argc, char **argv)
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7};
    int d = 3;
    int n = sizeof(arr) / sizeof(arr[0]);    //divide size of array by size of one (first) element

    rotateArr(arr, n, d);
  
    for (int i = 0; i < n; i++) 
        printf("%i ", arr[i]);
    printf("\n");
    
    return 0;
}

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):

// C Code to right rotate an array using Reversal Algorithm

#include <stdio.h>

// Function to reverse a portion of the array from start to end
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--;
    }
}

// Function to rotate an array by d elements to the right
void rotateArr(int arr[], int n, int d) {
    
    // 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);
}

int main(int argc, char **argv)
{
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7};
    int d = 3;
    int n = sizeof(arr) / sizeof(arr[0]);    //divide size of array by size of one (first) element

    rotateArr(arr, n, d);
  
    for (int i = 0; i < n; i++) 
        printf("%i ", arr[i]);
    printf("\n");
    
    return 0;
}

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.