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-pointer 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:
// 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-Pointer Method)
Implementation:
// 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-Pointer Method:
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-pointer method 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-pointer method is more efficient in terms of space usage. Both methods are useful and knowing them expands your problem-solving toolkit.
