LeetCode 186: Reverse Words in a String II

Problem Restatement

We are given a character array s.

The array contains words separated by single spaces. There are no leading spaces, no trailing spaces, and each pair of words is separated by exactly one space.

We need to reverse the order of the words in-place. The internal order of characters inside each word should stay the same. The problem requires solving it without allocating extra space.

Input and Output

Example function shape:

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

Examples

Example 1:

s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

This represents:

"the sky is blue"

After reversing the word order:

"blue is sky the"

So the array becomes:

["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:

s = ["a"]

There is only one word, so the array stays the same:

["a"]

First Thought: Split and Reverse

If this were a normal string problem, we could do:

words = text.split(" ")
words.reverse()
answer = " ".join(words)

But this problem gives us a mutable character array and asks us to modify it in-place.

So we should avoid creating a separate list of words.

We need to move characters inside the same array.

Key Insight

To reverse word order while keeping each word readable, use two reversal steps.

Start with:

the sky is blue

Reverse the whole array:

eulb si yks eht

Now the words are in the correct order, but each word is spelled backward.

So reverse each word individually:

blue is sky the

This gives the exact target.

Algorithm

1. Reverse the whole array.
2. Scan the array from left to right.
3. Whenever a word boundary is found, reverse that word.
4. Continue until all words are restored.

A word boundary is found when we hit a space or the end of the array.

Correctness

Reversing the entire array moves the last word to the front, the second last word after it, and so on.

However, this whole-array reversal also reverses the characters inside each word.

For example:

blue

becomes:

eulb

Then we reverse each word’s character range in-place.

This restores the internal character order of every word while preserving the reversed word order created by the first step.

Therefore, the final array contains the original words in reverse order, with each word spelled correctly.

Complexity

Here, n is len(s).

Implementation

class Solution:
    def reverseWords(self, s: list[str]) -> None:
        def reverse(left: int, right: int) -> None:
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1

        n = len(s)

        reverse(0, n - 1)

        start = 0

        for i in range(n + 1):
            if i == n or s[i] == " ":
                reverse(start, i - 1)
                start = i + 1

Code Explanation

The helper function reverses one range of the array:

def reverse(left: int, right: int) -> None:

It swaps characters from both ends:

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

After each swap, the pointers move inward:

left += 1
right -= 1

This line reverses the full character array:

reverse(0, n - 1)

Then we scan for word boundaries:

for i in range(n + 1):

We use n + 1 so that the final word is handled when i == n.

This condition detects the end of a word:

if i == n or s[i] == " ":

Then we reverse that word:

reverse(start, i - 1)

Finally, the next word starts after the space:

start = i + 1

Testing

def run_tests():
    s = Solution()

    arr = list("the sky is blue")
    s.reverseWords(arr)
    assert arr == list("blue is sky the")

    arr = list("a")
    s.reverseWords(arr)
    assert arr == list("a")

    arr = list("hello world")
    s.reverseWords(arr)
    assert arr == list("world hello")

    arr = list("one two three")
    s.reverseWords(arr)
    assert arr == list("three two one")

    arr = list("ab cd")
    s.reverseWords(arr)
    assert arr == list("cd ab")

    print("all tests passed")

run_tests()

Test meaning: