Given an array of integers, reverse its elements using recursion.
The array must be modified in place, without creating another array.
Example 1
Input: arr = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: The first element swaps with the last, the second with the second to last, and the middle remains in place, completely reversing the array order.
Example 2
Input: arr = [10, 20]
Output: [20, 10]
Explanation: The array has only two elements. Swapping the first and second elements gives the reversed array.
Approach
To reverse an array, the first element must exchange places with the last element, the second with the second-last, and so on.
Two pointers can represent the pair currently being handled:
startpoints to the left side.endpoints to the matching position on the right side.
After swapping these two elements, both pointers move inward. Once they meet or cross, every required pair has already been swapped and the array is reversed.
Algorithm
Use a recursive function with the array,
start, andendas parameters. The two indices mark the part of the array that still needs to be reversed.When
start >= end, return from the function. At this point, the pointers have met or crossed, which means all outer pairs have been placed correctly.Swap the elements at
startandendso that both values move to their reversed positions.Continue with
start + 1andend - 1, allowing the next recursive call to handle the smaller section between them.
Dry Run
Reverse Array Two Pointer Appraoch Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: void reverseHelper(vector<int>& nums, int start, int end) { // Base case: every pair has already been handled. if (start >= end) { return; } // Place the outer elements in their reversed positions. swap(nums[start], nums[end]); reverseHelper(nums, start + 1, end - 1); }public: void reverseArray(vector<int>& nums) { reverseHelper(nums, 0, nums.size() - 1); }};int main() { vector<int> nums = {1, 2, 3, 4, 5}; Solution solution; solution.reverseArray(nums); for (int value : nums) { cout << value << " "; } cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because approximately N / 2 pairs are swapped. Since constant factors are ignored, this simplifies to O(N).
Space Complexity: O(N), because the recursion creates approximately N / 2 call-stack frames, which is linear in terms of the array size.
FAQs
Q1. Does the approach work for an array with an odd number of elements?
Yes. The middle element does not need to move. The base case stops the recursion when the pointer reaches the middle, leaving that element unchanged.
Q2. What happens when the array is empty or contains one element?
No swap is required. The base case is reached immediately, and the array remains unchanged.
Q3. Why do both pointers move inward after every swap??
After swapping start and end, both positions are already in their correct reversed locations. Therefore, the next recursive call only needs to process the smaller section between them using start + 1 and end - 1.
Q4. Is the array truly reversed in place?
Yes. The elements are swapped inside the original array, and no second array is created. However, recursion still uses call-stack space.
Q5. Why does the recursion stop at the middle of the array?
Each swap fixes two positions at once. After the first half has been processed, every element in the second half has already been moved to its correct position.
Q6. Can the same problem be solved iteratively?
Yes. Two pointers can reverse the array using a loop in O(N) time and O(1) auxiliary space, avoiding the recursive call stack.
Be the first to add a comment.