Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Reverse an Array using recursion

EASYProblemSolveExternal Links

Description

You are given an array of integers. Your task is to reverse the array in place — meaning the first element should become the last, the second element should become the second last, and so on.

The reversal must modify the original array directly rather than creating a new one.

Examples

Example 1

Input: arr = [1, 4, 3, 2, 6, 5]

Output: [5, 6, 2, 3, 4, 1]

Explanation: After reversing, the element at position 0 (which was 1) moves to position 5, the element at position 1 (which was 4) moves to position 4, and so on. Every element swaps to its mirror position from the opposite end.

Example 2

Input: arr = [4, 5, 2]

Output: [2, 5, 4]

Explanation: The first element 4 and last element 2 swap positions. The middle element 5 remains in place because it is already at the center of the array. In odd-length arrays the center element never moves.

Example 3

Input: arr = [1]

Output: [1]

Explanation: A single-element array is already its own reverse. No swaps are needed.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 0 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

The simplest way to reverse an array is to create a brand-new array and fill it by reading the original array from back to front. Once the temporary array holds all the elements in reversed order, we copy everything back into the original array.

Imagine you have a row of books on a shelf. You take each book starting from the rightmost one and place it onto a second empty shelf, left to right. After you have moved every book, you put them all back onto the original shelf. The books are now in reverse order.

Step-by-Step Explanation

Let's trace through with arr = [1, 4, 3, 2, 6, 5]:

Step 1: Create an empty temporary array temp of the same size (6 elements).

  • temp = [_, _, _, _, _, _]

Step 2: Copy arr[5] = 5 into temp[0].

  • temp = [5, _, _, _, _, _]

Step 3: Copy arr[4] = 6 into temp[1].

  • temp = [5, 6, _, _, _, _]

Step 4: Copy arr[3] = 2 into temp[2].

  • temp = [5, 6, 2, _, _, _]

Step 5: Copy arr[2] = 3 into temp[3].

  • temp = [5, 6, 2, 3, _, _]

Step 6: Copy arr[1] = 4 into temp[4].

  • temp = [5, 6, 2, 3, 4, _]

Step 7: Copy arr[0] = 1 into temp[5].

  • temp = [5, 6, 2, 3, 4, 1]

Step 8: Copy all elements from temp back into arr.

  • arr = [5, 6, 2, 3, 4, 1]

Result: arr is now reversed.

Brute Force — Copy Into Temporary Array in Reverse — Watch how each element is read from the end of the original array and placed sequentially into a temporary array, building the reversed result.

Algorithm

  1. Create a temporary array temp of the same size as arr
  2. For each index i from 0 to n-1:
    • Set temp[i] = arr[n - 1 - i]
  3. For each index i from 0 to n-1:
    • Set arr[i] = temp[i]
  4. The array is now reversed in place

Code

#include <vector>
using namespace std;

class Solution {
public:
    void reverseArray(vector<int>& arr) {
        int n = arr.size();
        vector<int> temp(n);
        
        for (int i = 0; i < n; i++) {
            temp[i] = arr[n - 1 - i];
        }
        
        for (int i = 0; i < n; i++) {
            arr[i] = temp[i];
        }
    }
};
class Solution:
    def reverseArray(self, arr: list[int]) -> None:
        n = len(arr)
        temp = [0] * n
        
        for i in range(n):
            temp[i] = arr[n - 1 - i]
        
        for i in range(n):
            arr[i] = temp[i]
class Solution {
    public void reverseArray(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n];
        
        for (int i = 0; i < n; i++) {
            temp[i] = arr[n - 1 - i];
        }
        
        for (int i = 0; i < n; i++) {
            arr[i] = temp[i];
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array twice — once to copy elements into the temporary array and once to copy them back. Each pass visits every element exactly once, so the total work is 2n which simplifies to O(n).

Space Complexity: O(n)

We allocate a temporary array of the same size as the input. This extra memory grows linearly with the input size.

Why This Approach Is Not Efficient

The brute force approach uses O(n) extra space for the temporary array. While the time complexity is already O(n) — which is the best we can achieve since we must touch every element at least once — the space usage is wasteful.

Reversal is fundamentally a rearrangement problem. We are not creating new data; we are simply repositioning existing elements. If we can swap elements directly within the original array, we eliminate the need for any extra storage.

The key insight is that reversing an array means swapping each element at position i with the element at position n-1-i. These swaps are independent of each other and can be performed in place using only a single temporary variable for the swap itself — O(1) space instead of O(n).

Better Approach - Iterative Two Pointers

Intuition

Instead of copying elements into a new array, we can reverse in place by using two pointers — one starting at the beginning and one at the end. We swap the elements at these two pointers and then move both pointers toward the center. When the pointers meet or cross, every element has been placed in its correct reversed position.

Think of a line of people standing in a row who need to reverse their order. Instead of making everyone step out and reform, the first and last person simply trade places, then the second and second-to-last trade, and so on, working inward until no more swaps are needed.

Step-by-Step Explanation

Let's trace through with arr = [1, 4, 3, 2, 6, 5]:

Step 1: Initialize two pointers: left = 0, right = 5.

  • arr = [1, 4, 3, 2, 6, 5]

Step 2: Swap arr[left] and arr[right]: swap arr[0]=1 and arr[5]=5.

  • arr = [5, 4, 3, 2, 6, 1]
  • Move left to 1, right to 4.

Step 3: Swap arr[left] and arr[right]: swap arr[1]=4 and arr[4]=6.

  • arr = [5, 6, 3, 2, 4, 1]
  • Move left to 2, right to 3.

Step 4: Swap arr[left] and arr[right]: swap arr[2]=3 and arr[3]=2.

  • arr = [5, 6, 2, 3, 4, 1]
  • Move left to 3, right to 2.

Step 5: left (3) > right (2), so we stop. The array is fully reversed.

Result: arr = [5, 6, 2, 3, 4, 1]

Iterative Two Pointer Reversal — Watch how two pointers converge from opposite ends, swapping elements at each step until they meet in the middle.

Algorithm

  1. Set left = 0, right = n - 1
  2. While left < right:
    a. Swap arr[left] and arr[right]
    b. Increment left by 1
    c. Decrement right by 1
  3. The array is now reversed in place

Code

#include <vector>
using namespace std;

class Solution {
public:
    void reverseArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1;
        
        while (left < right) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
};
class Solution:
    def reverseArray(self, arr: list[int]) -> None:
        left = 0
        right = len(arr) - 1
        
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
class Solution {
    public void reverseArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

The two pointers start at opposite ends and each moves one step per iteration. They meet in the middle after n/2 iterations, so the loop runs n/2 times. Each iteration performs a constant-time swap. Overall: O(n/2) = O(n).

Space Complexity: O(1)

We use only two integer variables (left and right) plus one temporary variable for the swap. No additional data structures are allocated regardless of input size.

Why This Approach Is Not Efficient

The iterative two-pointer approach is actually optimal in terms of both time O(n) and space O(1). There is no asymptotically better solution for reversing an array.

However, this problem specifically asks us to solve it using recursion. Recursion provides an alternative way to think about the same two-pointer swap logic. Instead of using a while loop, we use the call stack to manage the state of the left and right pointers.

The recursive approach has the same O(n) time complexity but uses O(n) call stack space. Despite the extra space, understanding the recursive solution builds a critical foundation for problems where recursion is truly necessary — such as tree traversals, divide-and-conquer algorithms, and backtracking.

Optimal Approach - Recursion

Intuition

Recursion lets us express the two-pointer swap logic in a different way. Instead of writing a loop that repeats "swap and move inward," we write a function that does exactly one swap and then calls itself with updated pointers.

The idea is:

  • Base case: If the left pointer meets or crosses the right pointer, we have swapped all necessary pairs. Stop.
  • Recursive case: Swap the elements at left and right, then call the function again with left+1 and right-1.

Each recursive call handles one pair of elements, just like each iteration of the while loop. The call stack keeps track of where we are, replacing the loop variable.

Think of it as a relay race. The first runner (recursive call) swaps the outermost pair and passes the baton to the next runner, who swaps the next pair, and so on. When a runner finds there are no more pairs to swap, the race ends and everyone returns.

Step-by-Step Explanation

Let's trace through with arr = [1, 4, 3, 2, 6, 5]:

Step 1: Call reverse(arr, left=0, right=5).

  • left (0) < right (5) → proceed.
  • arr = [1, 4, 3, 2, 6, 5]

Step 2: Swap arr[0] and arr[5]: swap 1 and 5.

  • arr = [5, 4, 3, 2, 6, 1]

Step 3: Recurse: call reverse(arr, left=1, right=4).

  • left (1) < right (4) → proceed.

Step 4: Swap arr[1] and arr[4]: swap 4 and 6.

  • arr = [5, 6, 3, 2, 4, 1]

Step 5: Recurse: call reverse(arr, left=2, right=3).

  • left (2) < right (3) → proceed.

Step 6: Swap arr[2] and arr[3]: swap 3 and 2.

  • arr = [5, 6, 2, 3, 4, 1]

Step 7: Recurse: call reverse(arr, left=3, right=2).

  • left (3) ≥ right (2) → BASE CASE HIT. Return without doing anything.

Step 8: All recursive calls return. The array is fully reversed.

Result: arr = [5, 6, 2, 3, 4, 1]

Recursive Array Reversal — Call Stack Visualization — Watch how each recursive call swaps one pair of elements and delegates the remaining inner portion to the next call, until the base case is reached.

Algorithm

  1. Define a helper function reverse(arr, left, right)
  2. Base case: if left >= right, return (no more pairs to swap)
  3. Swap arr[left] and arr[right]
  4. Recursively call reverse(arr, left + 1, right - 1)
  5. Call the helper with left = 0 and right = n - 1 to start the process

Code

#include <vector>
using namespace std;

class Solution {
public:
    void reverseHelper(vector<int>& arr, int left, int right) {
        if (left >= right) {
            return;
        }
        swap(arr[left], arr[right]);
        reverseHelper(arr, left + 1, right - 1);
    }
    
    void reverseArray(vector<int>& arr) {
        reverseHelper(arr, 0, arr.size() - 1);
    }
};
class Solution:
    def reverseArray(self, arr: list[int]) -> None:
        def reverse_helper(left: int, right: int) -> None:
            if left >= right:
                return
            arr[left], arr[right] = arr[right], arr[left]
            reverse_helper(left + 1, right - 1)
        
        reverse_helper(0, len(arr) - 1)
class Solution {
    private void reverseHelper(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        reverseHelper(arr, left + 1, right - 1);
    }
    
    public void reverseArray(int[] arr) {
        reverseHelper(arr, 0, arr.length - 1);
    }
}

Complexity Analysis

Time Complexity: O(n)

Each recursive call performs one swap operation in O(1) time. The recursion goes n/2 levels deep (one level per pair of elements), so the total number of operations is n/2, which simplifies to O(n).

Space Complexity: O(n)

Although we do not allocate any additional data structures, the recursion itself uses the call stack. Each recursive call adds a frame to the stack, and we make n/2 calls before hitting the base case. Therefore the call stack space is O(n/2) = O(n). This is the tradeoff compared to the iterative approach which uses O(1) space.