How to Reverse an Array: Step-by-Step Guide

How to Reverse an Array: Step-by-Step Guide

Reversing an array is a common problem asked in many coding interviews and programming challenges and can be solved using various methods. In this article, we'll discuss two methods to reverse an array in C++: one using extra space and another using the two-pointers technique. Each method has its own advantages and trade-offs, which we'll explore in detail.

Solution 1: Using Extra Space (Copy and Paste Method)

Implementation:

// Solution 1: With Extra Space (Copy & Paste Method)
// Time Complexity: O(n)
// Space Complexity: O(n)
void reverseArray(int *arr, int n)
{
    int newArr[n];
    for (int i = 0; i < n; i++)
    {
        newArr[i] = arr[n - i - 1];
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] = newArr[i];
    }
}

Logic:

  1. Create a new array: newArr of the same size as the input array arr.

  2. First loop:

    • Iterate through the input array arr.

    • Copy elements from the end of arr to the beginning of newArr.

    • newArr[i] = arr[n - i - 1] reverses the order.

  3. Second loop:

    • Copy the reversed elements from newArr back to arr.

Time Complexity: O(n)

  • Explanation: Two separate loops, each iterating through the array once.

Space Complexity: O(n)

  • Explanation: An additional array of the same size is used.

Example:

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

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

  • Explanation: The elements are reversed in the new array and then copied back to the original array.


Solution 2: Without Extra Space (Two-Pointers Technique)

Implementation:

// Solution 2: Without Extra Space (Two-Pointers Technique)
// Time Complexity: O(n)
// Space Complexity: O(1)
void reverseArray(int *arr, int n)
{
    int start = 0;
    int end = n - 1;

    while (start < end)
    {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

Logic:

  1. Initialize two pointers:

    • start at the beginning of the array.

    • end at the end of the array.

  2. Loop:

    • Swap elements at start and end.

    • Move start forward and end backward until they meet in the middle.

Time Complexity: O(n)

  • Explanation: Single loop iterating through half the array.

Space Complexity: O(1)

  • Explanation: Only a few extra variables are used.

Example:

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

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

  • Explanation: Elements are swapped in place, reversing the array.


Comparison

  • Extra Space Method:

    • Pros: Simple and easy to understand.

    • Cons: Uses additional space equal to the size of the array.

    • Time Complexity: O(n)

    • Space Complexity: O(n)

  • Two-Pointers Technique:

    • Pros: Space efficient, as it only uses a constant amount of extra space.

    • Cons: Slightly more complex logic involving pointers.

    • Time Complexity: O(n)

    • Space Complexity: O(1)

Edge Cases

  • Single element array: An array with a single element remains the same after reversal.

  • Empty array: An empty array remains empty after reversal.

Additional Notes

  • The two-pointers technique is preferred for practical implementations due to its minimal space usage.

  • Understanding both methods is valuable for grasping different problem-solving approaches and space-time trade-offs.

Conclusion

Reversing an array is a fundamental problem that helps in understanding array manipulations and the trade-offs between time and space complexity. The method using extra space is straightforward and easy to implement, while the two-pointers technique is more efficient in terms of space usage. Both methods are useful and knowing them expands your problem-solving toolkit.