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;
}

### Explanation - The `reverseArray` function takes a vector of integers by reference and reverses it in place. - Two pointers, `left` and `right`, are used to swap elements from the start and end of the array. - The `while` loop continues until the `left` pointer is no longer less than the `right` pointer. ## Complexity Analysis - **Time Complexity**: O(n), where n is the number of elements in the array. Each element is swapped once. - **Space Complexity**: O(1), as no extra space is used apart from a few variables. ## Edge Cases - **Empty Array**: The function should handle an empty array without errors. - **Single Element Array**: The function should handle arrays with a single element correctly. ### Example Edge Cases - Input: `[]` → Output: `[]` - Input: `[1]` → Output: `[1]` ## Testing To test the solution comprehensively: - Use a variety of test cases, including empty arrays, single-element arrays, and arrays with multiple elements. - Verify the output manually or use assertions in the code. ### Example Test Cases cpp vector test1 = {}; // Empty array vector test2 = {1}; // Single element array vector test3 = {1, 2, 3, 4, 5}; // Multiple elements reverseArray(test1); reverseArray(test2); reverseArray(test3); // Expected outputs: [], [1], [5, 4, 3, 2, 1] ## Thinking and Problem-Solving Tips - Break down the problem into smaller steps. - Use diagrams to visualize the array and pointer movements. - Practice similar problems to strengthen your understanding of array manipulation. ## Conclusion Reversing an array is a fundamental problem that helps in understanding array manipulation and indexing. By implementing the solution manually, you gain deeper insights into how arrays work and improve your problem-solving skills. ## Additional Resources - [GeeksforGeeks - Array Reversal](https://www.geeksforgeeks.org/write-a-program-to-reverse-an-array-or-string/) - [LeetCode - Array Problems](https://leetcode.com/tag/array/) - [C++ Documentation](https://en.cppreference.com/w/cpp/container/vector) By practicing and exploring further, you can enhance your understanding and become proficient in solving array-related problems.