Reverse String

01 · Question

Reverse an array of characters in place using O(1) extra memory. Modify the existing array; do not return a new one.

Examples: [h,e,l,l,o] → [o,l,l,e,h]; [] → []; [a] → [a]. The Go snippets operate on ASCII bytes, matching the exercise's character constraints.

02 · Analysis

Swap the leftmost and rightmost remaining characters, then move inward. Stop when left≥right. The outside portion is already in its final position.

Iteration meets the requirement: O(n) time and O(1) auxiliary space. Recursion is a comparison only: it also mutates in place, but needs about n/2 active frames, hence O(n) auxiliary space. It does not meet the O(1)-space requirement and may exceed runtime depth limits. Both versions below produce the same mutations.

03 · Solution

Reference solution

1. Iterative solution: O(1) auxiliary space

1def reverseString(s: list[str]) -> None:
2    left, right = 0, len(s) - 1
3    while left < right:
4        s[left], s[right] = s[right], s[left]
5        left += 1
6        right -= 1

2. Recursive comparison: O(n) stack, exceeds the space requirement

1def reverseString(s: list[str]) -> None:
2    def visit(left, right):
3        if left >= right:
4            return
5        s[left], s[right] = s[right], s[left]
6        visit(left + 1, right - 1)
7    visit(0, len(s) - 1)

Pow(x, n)