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 (2 Pointer Method)
// 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.