☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Reverse an array

Easy TUF ID 342 A2Z

Java source ↗ Edit this article ↗

Problem

Given an array of N integers, reverse it: the element at index 0 should move to index N - 1, index 1 to N - 2, and so on. The problem sits on the recursion sheet, so the goal is to do the reversal recursively, ideally in place, after first understanding the loop version.

Constraints: 0 ≤ N ≤ 10^5 (the recursive versions are comfortable up to a few thousand; see the pitfalls). Elements may repeat and may be negative.

To keep the input intact for testing, every method below returns a reversed copy; the in-place logic is applied to a clone. Drop the clone() if you want to reverse the caller’s array directly.

Example 1

arr = [1, 2, 3, 4, 5]
answer = [5, 4, 3, 2, 1]     // odd length: the middle element 3 stays where it is

Example 2

arr = [1, 2, 3, 4]
answer = [4, 3, 2, 1]        // even length: every element moves

Example 3

arr = [7]
answer = [7]                 // one element (or none) is already reversed

Approach 1: Brute force with a second array

Intuition. The definition says element i goes to position n - 1 - i. If we are allowed a second array, we can place every element directly at its destination in a single pass. Nothing is swapped, so there is no risk of overwriting data we still need.

Algorithm.

  1. Allocate res of the same length.
  2. For every i, set res[n - 1 - i] = arr[i].
  3. Return res.
static int[] bruteForce(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) res[n - 1 - i] = arr[i];
    return res;
}

Complexity. Time O(n), one assignment per element. Space O(n) for the second array, which is the thing the next approaches remove.

Approach 2: Two pointers, iterative and in place

Intuition. Reversal pairs up index 0 with n - 1, 1 with n - 2, and so on. Each pair can simply be swapped, and the pairs are independent, so we can walk two pointers l and r inward from the ends and swap at each step. Once they meet or cross, every pair has been handled. For odd n the middle element is its own partner and is left alone.

Algorithm.

  1. Set l = 0, r = n - 1.
  2. While l < r: swap a[l] and a[r], then l++, r--.
  3. Return the array.
static int[] iterativeTwoPointers(int[] arr) {
    int[] a = arr.clone();
    int l = 0, r = a.length - 1;
    while (l < r) {
        int t = a[l]; a[l] = a[r]; a[r] = t;
        l++; r--;
    }
    return a;
}

Complexity. Time O(n): n / 2 swaps. Space O(1) beyond the array itself (the clone() is only for the tests).

Approach 3: Two pointers, recursive

Intuition. Replace the while loop with a recursive function whose parameters are the two pointers. The call reverse(a, l, r) means “reverse the sub-array a[l..r]”. It swaps the outer pair and then asks the recursion to reverse the inner sub-array a[l + 1 .. r - 1]. The sub-array shrinks by two on every call, and a sub-array of length 0 or 1 is already reversed, which gives the base case l >= r.

This is parameterised recursion: the state the loop kept in l and r is carried in the arguments, and the work (the swap) happens before the recursive call.

Algorithm.

  1. Start with reverse(a, 0, n - 1).
  2. In reverse(a, l, r): if l >= r, return.
  3. Swap a[l] and a[r], then call reverse(a, l + 1, r - 1).
static int[] recursiveTwoPointers(int[] arr) {
    int[] a = arr.clone();
    reverse(a, 0, a.length - 1);
    return a;
}

private static void reverse(int[] a, int l, int r) {
    if (l >= r) return;                     // base case: pointers met or crossed
    int t = a[l]; a[l] = a[r]; a[r] = t;    // swap the outer pair
    reverse(a, l + 1, r - 1);               // reverse the inner part
}

Dry run on arr = [1, 2, 3, 4, 5]:

call l r action array after
reverse(a, 0, 4) 0 4 swap 1 and 5 [5, 2, 3, 4, 1]
reverse(a, 1, 3) 1 3 swap 2 and 4 [5, 4, 3, 2, 1]
reverse(a, 2, 2) 2 2 l >= r, stop [5, 4, 3, 2, 1]

Complexity. Time O(n): about n / 2 calls. Space O(n) for the call stack, more precisely n / 2 + 1 frames.

Approach 4: Single pointer, recursive

Intuition. The second pointer is redundant: if the array length n is known, the partner of index i is always n - 1 - i. So a single index i starting at 0 is enough, and the recursion stops once i reaches the middle, i >= n / 2. Integer division makes this work for both parities: for n = 5 we stop at i = 2 (the middle element is untouched), for n = 4 we stop at i = 2 after swapping pairs (0, 3) and (1, 2).

Algorithm.

  1. Start with reverseFrom(a, 0).
  2. In reverseFrom(a, i): if i >= n / 2, return.
  3. Swap a[i] and a[n - 1 - i], then call reverseFrom(a, i + 1).
static int[] recursiveOnePointer(int[] arr) {
    int[] a = arr.clone();
    reverseFrom(a, 0);
    return a;
}

private static void reverseFrom(int[] a, int i) {
    int n = a.length;
    if (i >= n / 2) return;                 // base case: first half done, so the whole array is reversed
    int t = a[i]; a[i] = a[n - 1 - i]; a[n - 1 - i] = t;
    reverseFrom(a, i + 1);
}

Complexity. Time O(n), space O(n) for the stack, exactly as Approach 3. The one-pointer form is the one to remember because it generalises to “is this array/string a palindrome?”: replace the swap with a comparison.

Edge cases and pitfalls