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

Reversing an array means, rearranging the elements such that the last element becomes the first, the last-but-one element becomes the second, the third-to-the-last element becomes third; and so on.

Example:

Input:  [0, 1, 2, 3, 4, 5, 6, 7]  
Output:  [7, 6, 5, 4, 3, 2, 1, 0]

The number of elements in this example is even. If the number of elements is odd, the middle (center) element will not change its position.

An array can be reversed, using the temporary-array-technique, two pointers or single pointer.

Reversing an Array using Temporary Array in O(n) Time and O(n) Space

Here is the brute-force (naive) approach.

This involves:

- Creating a temporary array of same size as the original array;
- copying all elements from original array to the temporary array in reverse order;
- and finally, copying all the elements from temporary array back to the original array.

The algorithm essentially, takes the last element and put as the first element, takes the last-but-one element and puts as the second element, takes the third-to-the-last element and puts as the third element; and so on. This swapping continues until the middle of the array is reached. If the number of elements in the array is odd, then the middle element is not swapped.

With zero based indexing, the swapping statement is:

     temp[i] = arr[n - i - 1];

where i is the iterating index from 0, and n is the length (size) of the array.

When i=0, "temp[0] = arr[n - 0 – 1];" => "temp[0] = arr[n – 1];"
When i=1, "temp[1] = arr[n - 1 – 1];" => "temp[1] = arr[n – 2];"
When i=2, "temp[2] = arr[n - 2 – 1];" => "temp[1] = arr[n - 3];"

The following program illustrates this (read through the code and comments):

#include <stdio.h>

void reverseArray(int arr[], int n) {
    
    // Temporary array to store elements
    // in reversed order
    int temp[n];
  
    // Copy all elements from original array
    // to temp in reverse order
    for(int i = 0; i < n; i++)
        temp[i] = arr[n - i - 1];
  
    // Copy elements back to original 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 n = sizeof(arr) / sizeof(arr[0]);    //divide size of array by size of one (first) element

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

The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space for the for-loops and arrays respectively. The time complexity is actually O(2n) and the space complexity is actually O(2n). However, the coefficient (multiplier) is usually omitted when quoting the complexity.

The given array and the array in the reverseArray() function parameter list (parentheses) are the same one array (references).

Reversing an Array using Two Pointers in O(n) Time and O(n) Space

Two pointers refer to left (i) and right (j) indexes, such that left points at the start of the array and right points to the end of the array, initially.

While the left pointer is less than the right pointer, swap the elements at these two positions. After each swap, increment the left pointer and decrement the right pointer to move towards the center of the array. This will swap all the elements in the first half with their corresponding elements in the second half.

The following program illustrates this (read through the code and comments):

#include <stdio.h>

// Helper function to swap two numbers
void swap(int *a, int *b) {
    int temp = *a;    //temporary single variable and not temporary array
    *a = *b;
    *b = temp;
}

// function to reverse an array
void reverseArray(int arr[], int n) {
    int left = 0, right = n - 1;

    // Iterate till left would almost equal right
    while (left < right) {
        swap(&arr[left], &arr[right]);

        // Increment the left pointer
        left++;
        // Decrement the right pointer
        right--;
    }
}

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

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

Note the use of the swap() helper function, where int *a from the swap() function corresponds to &arr[left] in the called function, and int *b from the swap() function corresponds to &arr[right] in the called function. The whole program has just one array, given in the main section. The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space, for the for-loop and array respectively. O(n) space refers to the only array, which is the input array. The while-loop takes precisely O(1/2N) time, but the ½ (coefficient) has to be omitted when quoting the complexity.

Reversing an Array using Single Pointer in O(n) Time and O(n) Space

This algorithm iterates over the first half of the array and swaps each element with its corresponding element of the second half. So, while iterating over the first half, any element at index i is swapped with the element at index (n - i – 1). If the number of elements in the given array is odd, the center element is not swapped. left (i) is the single pointer. The following program illustrates this (read through the code and comments):

#include <stdio.h>

void reverseArray(int arr[], int n) {
    // swap arr[i] with arr[n - i - 1]
    for (int i = 0; i < n / 2; i++) {
        int temp = arr[i];    //temporary single variable and not temporary array
        arr[i] = arr[n - i - 1];
        arr[n - i - 1] = temp;
    }
}

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

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

n / 2 is integer division. This division discards the remainder. If the number of elements in the array is odd, say 9 for example, then the center (middle) index would be 4, whose element is not swapped. If the number of elements is even, say 8 for example, then the almost center (middle) left index would be 3, whose element has to be swapped with the almost center (middle) right element of index 4.

The output is:

    7 6 5 4 3 2 1 0 

achieved in O(n) time and O(n) space, for the for-loop and array respectively. O(n) space refers to the only array, which is the input array. The for-loop takes precisely O(1/2N) time, but the ½ has to be omitted when quoting the complexity.

Thanks for reading.