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

``````