Understanding the Problem

Reversing an array involves rearranging its elements in the opposite order. For instance, if we have an array [1, 2, 3, 4, 5], the reversed array would be [5, 4, 3, 2, 1].

Examples

Example 1:

Input: n = 5, arr = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

Explanation: The reverse of array [1, 2, 3, 4, 5] is [5, 4, 3, 2, 1]

Example 2:

Input: n = 4, arr = [1, 1, 2, 2]
Output: [2, 2, 1, 1]

Explanation: The reverse of array [1, 1, 2, 2] is [2, 2, 1, 1]

Approaches

1️⃣ Naive Approach

One straightforward approach is to create a new array and copy elements from the original array in reverse order.

Intuition:

To reverse an array, the objective is to reorder the elements such that the last element becomes the first and the second last becomes the second, and so forth. The straightforward approach involves creating a new array of the same size and populating it by iterating through the input array from end to start, thereby storing elements in reverse order.

Approach:

1. Declare a new array having the same size as the input array.
2. Iterate through the input array from the end to the beginning and for each element in the input array, store it in the corresponding position in the new array.
3. After the loop ends, the new array will contain the reversed elements.
4. Copy the elements back to the original array to get the reversed array.

Code Implementation:

#include <iostream>

void reverseArray(int arr[], int size) {
    int reversedArray[size];
    for (int i = 0; i < size; ++i) {
        reversedArray[i] = arr[size - 1 - i];
    }

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

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

    reverseArray(arr, size);

    // Output the reversed array
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

// OR
// This one iterates from last to first.
// Function to reverse array using an auxiliary array
    void reverse(int arr[], int n) {
        int* ans = new int[n];
        
        /* Fill new array with elements of 
        original array in reverse order */
        for (int i = n-1; i >= 0; i--) {
            ans[n-i-1] = arr[i];
        }
        
        // Copy the elements back to the original array
        for(int i=0; i < n; i++) {
            arr[i] = ans[i];
        }
        
        // Free the dynamically allocated memory
        delete[] ans; 
        
        // Return
        return;
    }

Complexity Analysis

• Time Complexity: O(N), where N is the number of elements in the array. This algorithm iterates through the array once to create the reversed array.
• Space Complexity: O(N), This is because it requires additional space for the reversed array, which has the same size as the original array.

2️⃣ In-Place Reversal

To optimize space usage, we can reverse the array in-place – without using additional storage. This can be achieved by swapping elements from both ends, gradually moving towards the center. This algorithm has a space complexity of 0(1) since it doesn't require additional storage.

Intuition:

To reverse an array in place without additional space, employ a swapping technique utilizing two pointers: one starting from the beginning of the array and the other from the end. By exchanging the elements at these pointers and progressively moving them toward the center, the array can be reversed efficiently within the same memory allocation. This method is both space-efficient and effective.

Approach:

1. Initialize a pointer start at the first index and another pointer end at the last index of the array.
2. Swap the elements pointed by start and end and increment start by 1 while decrementing end by 1 simultaneously.
3. Repeat the process for the first n/2 elements, where n is the length of the array.

Code Implementation:

#include <iostream>

void reverseArrayInPlace(int arr[], int size) {
    int start = 0;
    int end = size - 1;

    while (start < end) {
        // Swap elements at start and end indices
        // std::swap(arr[start], arr[end]); // you can use this in competitive programming else manually do so.
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        // Move indices towards the center
        ++start;
        --end;
    }
}

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

    reverseArrayInPlace(arr, size);

    // Output the reversed array
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), This also has the same time complexity of O(N). The loop runs until the start index surpasses the end index. In each iteration two elements are swapped, and the indices are moved towards the center.
• Space Complexity: O(1), The space complexity of the in-place reversal algorithm is O(1). This is because it doesn't use any additional space that scales with the input size. The algorithm only requires a constant amount of extra space for temporary variables (like start and end indices), regardless of the array size.