Reverse Array in C++ with O(n) Time Complexity
## Understanding the Problem The task is to reverse an array of integers without using built-in functions. This means we need to manually implement the logic to reverse the array. ### Core Challenge The main challenge is to reverse the array efficiently without using helper functions like `reverse()`. This requires understanding how to manipulate array indices and swap elements. ### Significance and Applications Reversing an array is a fundamental problem in computer science with applications in data processing, algorithms, and more. Understanding how to manually reverse an array helps in grasping array manipulation and indexing. ### Potential Pitfalls - Mismanaging array indices can lead to out-of-bound errors. - Not handling edge cases like empty arrays or single-element arrays. ## Approach ### Naive Solution A naive approach would be to create a new array and copy elements from the original array in reverse order. However, this approach uses extra space, which is not optimal. ### Optimized Solution A more efficient approach is to reverse the array in place using the two-pointer technique. This method involves swapping elements from the start and end of the array, moving towards the center. ### Thought Process 1. Initialize two pointers: one at the beginning (`left`) and one at the end (`right`) of the array. 2. Swap the elements at these pointers. 3. Move the `left` pointer one step to the right and the `right` pointer one step to the left. 4. Repeat the process until the `left` pointer is greater than or equal to the `right` pointer. ## Algorithm 1. Initialize `left` to 0 and `right` to the last index of the array. 2. While `left` is less than `right`: - Swap the elements at `left` and `right`. - Increment `left` and decrement `right`. 3. The array is now reversed. ## Code Implementation
#include <iostream>
#include <vector>
using namespace std;
// Function to reverse the array in place
void reverseArray(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
// Swap elements until the two pointers meet
while (left < right) {
// Swap the elements at left and right
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
// Move the pointers towards the center
left++;
right--;
}
}
int main() {
vector<int> nums = {2, 9, 1, 5, 8};
// Reverse the array
reverseArray(nums);
// Print the reversed array
for (int num : nums) {
cout << num << " ";
}
return 0;
}