# 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

| Item | Meaning |
|---|---|
| Input | A character array `s` |
| Output | Nothing is returned |
| Mutation | Modify `s` in-place |
| Rule | Reverse word order, not letters inside each final word |
| Space requirement | Use constant extra space |

Example function shape:

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

## Examples

Example 1:

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

This represents:

```text
"the sky is blue"
```

After reversing the word order:

```text
"blue is sky the"
```

So the array becomes:

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

Example 2:

```python
s = ["a"]
```

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

```python
["a"]
```

## First Thought: Split and Reverse

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

```python
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:

```text
the sky is blue
```

Reverse the whole array:

```text
eulb si yks eht
```

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

So reverse each word individually:

```text
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:

```text
blue
```

becomes:

```text
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is reversed at most twice |
| Space | `O(1)` | Only pointer variables are used |

Here, `n` is `len(s)`.

## Implementation

```python
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:

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

It swaps characters from both ends:

```python
s[left], s[right] = s[right], s[left]
```

After each swap, the pointers move inward:

```python
left += 1
right -= 1
```

This line reverses the full character array:

```python
reverse(0, n - 1)
```

Then we scan for word boundaries:

```python
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:

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

Then we reverse that word:

```python
reverse(start, i - 1)
```

Finally, the next word starts after the space:

```python
start = i + 1
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"the sky is blue"` | Main example with multiple words |
| `"a"` | Single word case |
| `"hello world"` | Two words |
| `"one two three"` | Odd number of words |
| `"ab cd"` | Short equal-length words |