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

    reverseArray <- function (arr) { 
        n = length(arr);
    
        # Temporary array to store elements
        # in reversed order
        temp <- vector("integer", length = n);
  
        # Copy all elements from original array
        # to temp in reverse order
        for (i in 1:n) 
            temp[i] <- arr[n - i + 1];
  
        return (temp);
    }

#main area
    arr = c(0, 1, 2, 3, 4, 5, 6, 7);
        
    arr <- reverseArray(arr);     # Assign the returned array back 
            
    for (i in 1:length(arr))  
        cat(arr[i], " ", sep="");
    cat("\n");

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

# Helper function to swap two numbers
swap <- function(arr, a, b) {
  temp <- arr[a]     # temporary single variable and not temporary array
  arr[a] <- arr[b]
  arr[b] <- temp
  return(arr)    # R passes by value, so we must return the modified array
}

reverseArray <- function(arr) {
  n <- length(arr)
  left <- 1      # 1-based indexing
  right <- n     # 1-based indexing
  
  # Iterate till left would almost equal right
  while (left < right) {
    arr <- swap(arr, left, right)
    
    # Increment the left pointer
    left <- left + 1
    # Decrement the right pointer
    right <- right - 1
  }
  return(arr)
}

# main area
arr <- c(0, 1, 2, 3, 4, 5, 6, 7)

arr <- reverseArray(arr)

for (i in 1:length(arr)) {
  cat(arr[i], " ", sep="")
}
cat("\n")

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

    reverseArray <- function(arr) { 
        n = length(arr);
    
        # swap arr[i] with arr[n - i + 1]
        for (i in 1:(n/2))    {    #integer division
            temp = arr[i];    #temporary single variable and not temporary array
            arr[i] = arr[n - i + 1];
            arr[n - i + 1] = temp;
        }
        return(arr)    # Return the modified array
    }

# main area
    arr = c(0, 1, 2, 3, 4, 5, 6, 7);
        
    arr <- reverseArray(arr);
            
    for (i in 1:length(arr)) {
        cat(arr[i], " ", sep="")
    }
    cat("\n")

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.