Reverse the Elements of a Given Array In-Place
Brute Force Approach
Idea
The brute force method to reverse an array is by creating a new array and copying elements from the original array in reverse order.
Steps
- Create a new array.
- Traverse the original array from the last element to the first.
- Copy each element into the new array.
Time Complexity
- O(n), where
n is the size of the array, because we are traversing the array once.
Space Complexity
- O(n) since we are creating an additional array.
Example Code
Dry Run
For array [1, 2, 3, 4, 5]:
- Traverse from right to left: push
5, 4, 3, 2, 1 into the new array.
- Return the new array
[5, 4, 3, 2, 1].
Efficient Approach (In-Place Reversal)
Idea
To reverse the array in place without using any extra space, we can swap the first element with the last, the second with the second-last, and so on.
Steps
- Initialize two pointers:
left at the beginning of the array and right at the end.
- Swap the elements at
left and right.
- Move the pointers towards the center and repeat until the entire array is reversed.
Time Complexity
- O(n) because we are making one pass through the array.
Space Complexity
- O(1) as no additional space is used apart from a few temporary variables for swapping.
Example Code
Dry Run
For array [1, 2, 3, 4, 5]:
- Swap
1 and 5, resulting in [5, 2, 3, 4, 1].
- Swap
2 and 4, resulting in [5, 4, 3, 2, 1].
- Since the
left and right pointers meet at the center, stop.
Example Test Cases
Test Case 1
Input: [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Test Case 2
Input: [7, 8, 9]
Output: [9, 8, 7]
Test Case 3
Input: []
Output: [] (Empty array)
Test Case 4
Input: [1]
Output: [1] (Single element array)
Complexity Analysis
Brute Force Approach
- Time Complexity:
O(n) (due to traversal)
- Space Complexity:
O(n) (due to the use of an additional array)
Efficient Approach
- Time Complexity:
O(n) (single traversal of the array)
- Space Complexity:
O(1) (constant space, in-place reversal)
Conclusion
The brute force approach is simple but inefficient due to the additional space required. The in-place reversal is more efficient, especially for large arrays, as it uses constant space while maintaining linear time complexity.