Reverse String

The problem. Reverse an array of characters s in place: modify the input array, using O(1) extra memory.

Example

s = ["h", "e", "l", "l", "o"]       ->  ["o", "l", "l", "e", "h"]
s = ["H", "a", "n", "n", "a", "h"]  ->  ["h", "a", "n", "n", "a", "H"]

The idea: a smaller copy of the same problem

Reversing s[left..right] means swapping the two end letters and then reversing s[left + 1..right − 1] — which is the same problem on a range two letters shorter. The base case is a range with zero or one letters: nothing to do. Recursion expresses that in three lines — but watch the memory: n/2 calls pile up on the call stack, which breaks the O(1) memory rule.

1. Recursion on the shrinking range

1function reverseString(s) {2  const reverse = (left, right) => {3    if (left >= right) return;                     // 0 or 1 letters left: done4    [s[left], s[right]] = [s[right], s[left]];     // swap the ends5    reverse(left + 1, right - 1);                  // reverse the middle6  };7  reverse(0, s.length - 1);8}

Time O(n), space O(n) — n/2 frames on the call stack. Correct, but the problem asks for O(1) extra memory, and 100,000 letters would mean 50,000 frames: a stack overflow in Python.

2. Two pointers in a loop

The recursion is a tail call — nothing happens after it — so it turns straight into a loop: the parameters become two variables that move inwards.

1function reverseString(s) {2  let left = 0, right = s.length - 1;3  while (left < right) {4    [s[left], s[right]] = [s[right], s[left]];   // swap the ends5    left++;                                      // then move inwards6    right--;7  }8}

Time O(n), space O(1). The same steps without the call stack. This is the general lesson: a tail-recursive function always becomes a loop by turning its parameters into variables.

Comparing the approaches

Edge cases to test

Variations