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 ofnewArr
.newArr[i] = arr[n - i - 1]
reverses the order.
3. Second loop:
- Copy the reversed elements from
newArr
back toarr
.
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
andend
.Move
start
forward andend
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.
Top comments (0)