LeetCode 186 - Reverse Words in a String II

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

The problem asks us to reverse the order of words in a character array s in-place. Each word is a contiguous sequence of non-space characters, and words are separated by exactly one space. The input array does not have leading or trailing spaces, so we do not need to handle extra spaces at the ends. The expected output is the same array s but with the order of words reversed, while maintaining the characters of each word in their original order.

For example, given s = ["t","h","e"," ","s","k","y"], the words are "the" and "sky". After reversing the word order, the array should become ["s","k","y"," ","t","h","e"]. The key constraint is in-place modification, so no additional arrays should be created to store words separately.

Important edge cases include inputs with only one word, very short arrays, or arrays containing a single character. Since s is guaranteed to have at least one word and words are separated by a single space, we do not need to handle multiple spaces or empty strings.

Approaches

A naive brute-force approach would be to split the character array into words using a temporary array, reverse the list of words, and then reassemble them back into s. While this produces the correct result, it uses extra space proportional to the number of characters or words, violating the in-place requirement.

The key insight for an optimal approach is that reversing the entire array and then reversing each individual word produces the desired result. Reversing the entire array moves the last word to the first position, the second-to-last to the second position, and so on. However, this also reverses the characters within each word, so we need a second pass to reverse characters within each word to restore their original order.

This approach uses a two-pass in-place reversal with two pointers and does not require additional memory, satisfying the problem constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Split array into words, reverse words, reassemble array using extra memory
Optimal	O(n)	O(1)	Reverse entire array, then reverse each word individually in-place

Algorithm Walkthrough

Reverse the entire array s from start to end. This places the last word in the first position, the second-to-last in the second position, etc. Characters of each word are reversed, but word positions are correct.
Initialize a pointer start to track the beginning of each word. Iterate through the array with an index end.
Identify word boundaries. When you encounter a space ' ' or reach the end of the array, the current word runs from start to end - 1. Reverse the characters in this range to restore the original word order.
Update start to the index after the space to begin tracking the next word.
Continue this process until all words have been reversed individually. At the end, the array s contains the words in reversed order, with each word's characters in the correct order.

Why it works: Reversing the entire array correctly positions the words in reverse order but flips the characters. Reversing each word individually restores the character order within each word, producing the desired output. This approach guarantees correctness because the two reversals together are equivalent to reversing the word order while keeping word characters intact.

Python Solution

from typing import List

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

        # Step 1: Reverse the entire array
        reverse(0, len(s) - 1)

        # Step 2: Reverse each word individually
        start = 0
        for end in range(len(s) + 1):
            if end == len(s) or s[end] == ' ':
                reverse(start, end - 1)
                start = end + 1

Implementation Explanation: The helper function reverse swaps characters between two indices in the array. We first reverse the entire array to position the words in reversed order. Then, we traverse the array, detecting spaces to find word boundaries, and reverse each word in-place. The use of len(s) + 1 in the loop ensures the last word is reversed when end reaches the array length.

Go Solution

func reverseWords(s []byte) {
    // Helper function to reverse a segment of the array
    reverse := func(l, r int) {
        for l < r {
            s[l], s[r] = s[r], s[l]
            l++
            r--
        }
    }

    // Step 1: Reverse the entire array
    reverse(0, len(s)-1)

    // Step 2: Reverse each word individually
    start := 0
    for end := 0; end <= len(s); end++ {
        if end == len(s) || s[end] == ' ' {
            reverse(start, end-1)
            start = end + 1
        }
    }
}

Go-specific Notes: The logic mirrors the Python solution. Slices in Go are mutable, so we can modify s in-place. We use an inline helper function for reversals. Unlike Python, there is no need for type hints. Using end <= len(s) ensures the last word gets reversed correctly.

Worked Examples

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

Step 1: Reverse entire array:

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

Step 2: Reverse each word individually:

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

Final array:

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

Example 2: s = ["a"]

Step 1: Reverse entire array → unchanged.

Step 2: Reverse each word individually → unchanged.

Final array:

["a"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited at most twice: once during the full reversal and once during individual word reversals
Space	O(1)	Reversal is done in-place using two pointers, no extra memory is allocated

The algorithm scales linearly with the length of the array and uses constant extra space, making it optimal for large inputs up to 10^5 characters.

Test Cases

# Provided examples
assert (s := ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]) and Solution().reverseWords(s) or s == ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]  # multiple words
assert (s := ["a"]) and Solution().reverseWords(s) or s == ["a"]  # single word

# Edge cases
assert (s := ["h","i"]) and Solution().reverseWords(s) or s == ["h","i"]  # two-letter word
assert (s := ["h","e","l","l","o"," ","w","o","r","l","d"]) and Solution().reverseWords(s) or s == ["w","o","r","l","d"," ","h","e","l","l","o"]  # two words
assert (s := ["x"," ","y"," ","z"]) and Solution().reverseWords(s) or s == ["z"," ","y"," ","x"]  # single-character words

Test	Why
`["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]`	Validates multiple words with spaces
`["a"]`	Single word edge case
`["h","i"]`	Small word, array length >1 but no spaces
`["h","e","l","l","o"," ","w","o","r","l","d"]`	Two words to check space handling
`["x"," ","y"," ","z"]`	Single-character words

Edge Cases

Single-word array: An array like ["a","b","c"] should remain unchanged after reversal of words. Our implementation handles this by reversing the whole array and then reversing the only word, which restores the original array.

Single-character words: An array like `["x"," ","y"," ","z