Reverse String

NeetCode: Reverse String · LeetCode: 344. Reverse String · Difficulty: Easy

Write a function that reverses a character array in place, using O(1) extra memory.

Example

Text

Input:  ['h', 'e', 'l', 'l', 'o']         Output: ['o', 'l', 'l', 'e', 'h']
Input:  ['H', 'a', 'n', 'n', 'a', 'h']    Output: ['h', 'a', 'n', 'n', 'a', 'H']

Brute force: copy into a second buffer

Read the array from the end to the start into a new array, then copy it back. The extra array breaks the O(1) memory requirement.

Java

import java.util.Arrays;

class Solution {
    public void reverseString(char[] s) {
        char[] rev = new char[s.length];
        for (int i = 0; i < s.length; i++) {
            rev[i] = s[s.length - 1 - i];
        }
        for (int i = 0; i < s.length; i++) {
            s[i] = rev[i];
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[] a = {'h', 'e', 'l', 'l', 'o'};
        sol.reverseString(a);
        System.out.println(Arrays.toString(a));
        char[] b = {'H', 'a', 'n', 'n', 'a', 'h'};
        sol.reverseString(b);
        System.out.println(Arrays.toString(b));
        char[] c = {};
        sol.reverseString(c);
        System.out.println(Arrays.toString(c));
    }
}

Output

[o, l, l, e, h]
[h, a, n, n, a, H]
[]

Time: O(n). Space: O(n).

Optimal: swap from both ends

Put one pointer at the start and one at the end. Swap the two characters (Java has no swap method for arrays, so a temporary char holds one value), move the pointers toward each other, and stop when they meet. Every character is moved straight to its final position, so nothing else needs storing. The middle character of an odd-length array stays where it is.

Java

import java.util.Arrays;

class Solution {
    public void reverseString(char[] s) {
        int l = 0, r = s.length - 1;
        while (l < r) {
            char tmp = s[l];
            s[l] = s[r];
            s[r] = tmp;
            l++;
            r--;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        char[] a = {'h', 'e', 'l', 'l', 'o'};
        sol.reverseString(a);
        System.out.println(Arrays.toString(a));
        char[] b = {'H', 'a', 'n', 'n', 'a', 'h'};
        sol.reverseString(b);
        System.out.println(Arrays.toString(b));
        char[] c = {};
        sol.reverseString(c);
        System.out.println(Arrays.toString(c));
    }
}

Output

[o, l, l, e, h]
[h, a, n, n, a, H]
[]

Time: O(n). Space: O(1).

For an empty array r starts at -1, so l < r is false and the loop does not run. String is immutable, so in-place reversal needs a char[]; StringBuilder.reverse() does a similar job for a builder.