Reverse String

How it works

The most efficient approach uses two pointers starting at opposite ends of the array. We swap the characters at these pointers, then move them toward each other. When the pointers meet or cross, every character has been swapped exactly once, and the array is reversed. This achieves O(1) space since we only swap in place.

Steps

1. Initialize two pointers: l at index 0 and r at the last index.
2. While l < r:
   • Swap s[l] and s[r].
   • Increment l and decrement r.
3. The array s is now reversed in place.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Using Incorrect Loop Termination Condition

When using two pointers, the loop should terminate when l >= r, not when l > r. Using l != r works for odd-length strings but is less intuitive. The condition l < r correctly handles both even and odd length arrays.

Returning a New String Instead of Modifying In-Place

The problem requires modifying the input array in-place. A common mistake is creating a new reversed array or string and returning it, which violates the in-place requirement and uses unnecessary extra space.

from typing import List

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

class Solution {
public:
    void reverseString(vector<char>& s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            swap(s[l++], s[r--]);
        }
    }
};