Reversing the order of elements in an Array Data Structure

Reversing an array involves re-arranging the order of all its elements such that the first element becomes the last, the second element becomes the second last element, and so on. For example:

Array Before Reversal:

[ A | B | C | D | E ]

Array After Reversal:

[ E | D | C | B | A ]

Techniques for Reversing an Array

Let’s dive into few common techniques used for reversing arrays:

Iterative Approach Using Extra Space

This method is straightforward but is less memory-efficient due to creation of a new array.

Algorithm:

  • Create a temporary array with same size as the original.
  • Traverse the original array from end to start and copy the elements into the new array from start to the end.
  • Finally, replace the original array with the new reversed array.

#include <stdio.h>
#include <stdlib.h>

void reverseArray(int *arr, int size) {
  // Create a new array to store the reversed elements
  int *reversedArr = malloc(size * sizeof(int));

  // Index for original array (traversing from end to start)
  int ri = size - 1;

  // Index for reversed array (filling from start to end)
  int i = 0;

  // Copy elements from original array to reversed array in reverse order
  while (ri >= 0) {
    reversedArr[i] = arr[ri];
    ri--;
    i++;
  }

  // Copy reversed elements back to the original array
  for (i = 0; i < size; i++) {
    arr[i] = reversedArr[i];
  }

  // Free the memory allocated for the reversed array
  free(reversedArr);
}

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int size = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  reverseArray(arr, size);

  printf("Reversed array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

Time Complexity: O(N) - The loop iterates through all N elements of the original array once.

Space Complexity: O(N) - A temporary array of size N is created to store the reversed elements.

Iterative In-Place Approach (Two-Pointer Technique)

In-place approach involves using two-pointer technique to efficiently reverse all elements in the Array without using any extra space.

Algorithm:

  • Initialize two pointers, left pointing to the beginning of the array and right pointing to the last element.
  • Swap the elements present at the left and right positions.
  • Increment the left pointer and decrement the right pointer.
  • Continue performing the last two steps until the left and right pointers meet or cross each other.

#include <stdio.h>

void reverseArray(int arr[], int size) {
  // Initialize pointers to the beginning and end of the array
  int leftIndex = 0;
  int rightIndex = size - 1;

  // Loop until the pointers meet or cross
  while (leftIndex < rightIndex) {
    // Swap elements at left and right indices
    int temp = arr[leftIndex];
    arr[leftIndex] = arr[rightIndex];
    arr[rightIndex] = temp;

    // Move pointers towards each other
    leftIndex++;
    rightIndex--;
  }
}

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int size = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }

  reverseArray(arr, size);

  printf("\nReversed array: ");
  for (int i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

Time Complexity: O(N) - The loop iterates a maximum of N/2 times (from start to middle) as elements are swapped in pairs.

Space Complexity: O(1) - The algorithm uses constant extra space for the two pointers (left and right).

Recursive In-Place Approach

The recursive approach also modifies the array in-place, but it does so by breaking the problem down into smaller subproblems. While elegant, it is not the most space-efficient solution for large arrays due to recursion’s stack space overhead.

Algorithm:

  • Define a function that takes the array, left, and right indices as arguments.
  • Base case: If left is greater than or equal to right, it means that the array is reversed already reversed.
  • Otherwise, swap the elements at left and right.
  • Recursively call the function with left + 1 and right - 1.

#include <stdio.h>

void reverseArray(int arr[], int leftIndex, int rightIndex) {
  // Base case: If left index is greater than or equal to right index, the array is already reversed
  if (leftIndex >= rightIndex) {
    return;
  }

  // Swap elements at left and right indices
  int temp = arr[leftIndex];
  arr[leftIndex] = arr[rightIndex];
  arr[rightIndex] = temp;

  // Recursively call the function with updated indices
  reverseArray(arr, leftIndex + 1, rightIndex - 1);
}

int main() {
  int arr[] = {1, 2, 3, 4, 5};
  int arrLength = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  for (int i = 0; i < arrLength; i++) {
    printf("%d ", arr[i]);
  }

  reverseArray(arr, 0, arrLength - 1);

  printf("\nReversed array: ");
  for (int i = 0; i < arrLength; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

Time Complexity: O(N) - Function is recursively called for N/2 times

Space Complexity: O(N) - Due to stack space consumed by N/2 recursive function calls.

Built-in Functions (if applicable)

Learning all previous approach helps in understanding the different algorithms which could be used as building blocks for more complicated use-cases. But if you just need to reverse an array, many programming languages offer built-in functions or methods to reverse arrays which can be conveniently used to reverse arrays with just a single line of code.


arr = [1, 2, 3, 4, 5]
print("Original array:", arr)

arr.reverse()
print("Reversed array:", arr)