How to Reverse an Array: Step-by-Step Guide
Tags: algorithms, computerscience, cpp, coding
Published: 2024-06-03 10:59:29

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**:

```cpp
// 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**:

```cpp
// 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.

---