LeetCode 344: Reverse String

Problem Restatement

We are given an array of characters s.

Reverse the array in place.

This means we must modify the original array directly and use only O(1) extra memory. The function should not return a new array. It should change s itself.

For example:

["h", "e", "l", "l", "o"]

should become:

["o", "l", "l", "e", "h"]

Input and Output

Function shape:

def reverseString(s: list[str]) -> None:
    ...

Examples

Example 1:

Input:  s = ["h","e","l","l","o"]
Output:     ["o","l","l","e","h"]

Example 2:

Input:  s = ["H","a","n","n","a","h"]
Output:     ["h","a","n","n","a","H"]

First Thought: Build a New Reversed Array

A simple solution is to create another array and copy characters from the end of s to the beginning.

class Solution:
    def reverseString(self, s: list[str]) -> None:
        reversed_s = []

        for i in range(len(s) - 1, -1, -1):
            reversed_s.append(s[i])

        for i in range(len(s)):
            s[i] = reversed_s[i]

This produces the correct final array, but it uses O(n) extra memory.

The problem requires O(1) extra memory, so we should avoid a second array.

Key Insight

To reverse an array in place, swap symmetric positions.

The first character should move to the last position.

The last character should move to the first position.

Then the second character should swap with the second-to-last character.

Continue moving inward.

Use two pointers:

At each step, swap:

s[left], s[right] = s[right], s[left]

Then move both pointers inward.

Algorithm

1. Set left = 0.
2. Set right = len(s) - 1.
3. While left < right:
   1. Swap s[left] and s[right].
   2. Increment left.
   3. Decrement right.
4. Stop when the pointers meet or cross.

Walkthrough

Use:

s = ["h", "e", "l", "l", "o"]

Start:

left = 0
right = 4

Swap s[0] and s[4]:

["o", "e", "l", "l", "h"]

Move inward:

left = 1
right = 3

Swap s[1] and s[3]:

["o", "l", "l", "e", "h"]

Move inward:

left = 2
right = 2

Now left is not less than right, so we stop.

The array is reversed.

Correctness

The algorithm swaps characters in symmetric positions.

At the first step, the character originally at the beginning moves to the end, and the character originally at the end moves to the beginning.

After each swap, both swapped positions are final and never touched again.

Then the pointers move inward, so the algorithm repeats the same operation on the remaining unreversed middle section.

When the pointers meet or cross, every pair of symmetric positions has been swapped. For odd-length arrays, the middle character stays in place, which is correct.

Therefore, the array is reversed in place.

Complexity

Implementation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        left = 0
        right = len(s) - 1

        while left < right:
            s[left], s[right] = s[right], s[left]

            left += 1
            right -= 1

Code Explanation

Initialize the two pointers:

left = 0
right = len(s) - 1

The loop continues while there is still a pair to swap:

while left < right:

Swap the two characters:

s[left], s[right] = s[right], s[left]

Move inward:

left += 1
right -= 1

The function does not return anything because LeetCode checks the modified array.

Testing

def run_tests():
    sol = Solution()

    s = ["h", "e", "l", "l", "o"]
    sol.reverseString(s)
    assert s == ["o", "l", "l", "e", "h"]

    s = ["H", "a", "n", "n", "a", "h"]
    sol.reverseString(s)
    assert s == ["h", "a", "n", "n", "a", "H"]

    s = ["a"]
    sol.reverseString(s)
    assert s == ["a"]

    s = ["a", "b"]
    sol.reverseString(s)
    assert s == ["b", "a"]

    s = ["1", "2", "3", "4"]
    sol.reverseString(s)
    assert s == ["4", "3", "2", "1"]

    print("all tests passed")

run_tests()

Test meaning: