Code Implementation

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        def reverse(l, r):
            while l < r:
                s[l], s[r] = s[r], s[l]
                l += 1
                r -= 1

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

class Solution {
public:
    void reverseWords(vector<char>& s) {
        auto reverse = [&s](int l, int r) {
            while (l < r) {
                swap(s[l++], s[r--]);
            }
        };
        int n = s.size();
        // Step 1: Reverse the whole string
        reverse(0, n - 1);
        // Step 2: Reverse each word
        int start = 0;
        for (int end = 0; end <= n; ++end) {
            if (end == n || s[end] == ' ') {
                reverse(start, end - 1);
                start = end + 1;
            }
        }
    }
};
      

class Solution {
    public void reverseWords(char[] s) {
        // Helper function to reverse a portion of the array
        voidReverse(s, 0, s.length - 1);
        int start = 0;
        for (int end = 0; end <= s.length; end++) {
            if (end == s.length || s[end] == ' ') {
                voidReverse(s, start, end - 1);
                start = end + 1;
            }
        }
    }
    private void voidReverse(char[] s, int l, int r) {
        while (l < r) {
            char temp = s[l];
            s[l++] = s[r];
            s[r--] = temp;
        }
    }
}
      

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseWords = function(s) {
    function reverse(l, r) {
        while (l < r) {
            [s[l], s[r]] = [s[r], s[l]];
            l++;
            r--;
        }
    }
    let n = s.length;
    // Step 1: Reverse the whole string
    reverse(0, n - 1);
    // Step 2: Reverse each word
    let start = 0;
    for (let end = 0; end <= n; end++) {
        if (end === n || s[end] === ' ') {
            reverse(start, end - 1);
            start = end + 1;
        }
    }
};
      

Problem Description

Given a character array s representing a string, reverse the order of the words in-place. Each word is separated by a single space, and there are no leading or trailing spaces in the input. You must perform the operation in-place with O(1) extra space.

• You cannot use extra arrays or strings to store the result.
• Each word must remain intact (the letters in each word are not reversed).
• Only the order of the words should be reversed.
• There is only one valid solution for each input.

For example, given s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"], after calling the function, s should be ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"].

Thought Process

At first glance, the problem seems simple: reverse the words in a string. However, the requirement to do this in-place without using extra space or data structures makes it more challenging.

The brute-force approach would be to split the string into words, reverse the array of words, and rejoin them, but this would require extra space for the split and join operations, which is not allowed.

To solve this in-place, we need to carefully manipulate the array so that we only use swaps and do not allocate new arrays. The insight is to use the reverse operation, which can be performed in-place, to reorder the words:

• First, reverse the entire array. This puts the words in the correct reversed order, but each word is also reversed.
• Then, for each word, reverse its letters to restore the original word order.

This two-step reverse process is a classic trick for in-place reversal of word order.

Solution Approach

Let's break down the in-place solution step by step:

1. Reverse the entire array:
   • Swap the first and last characters, then the next pair, and so on, until the entire array is reversed.
   • After this step, the words are in the reversed order, but the letters of each word are also reversed.
2. Reverse each word individually:
   • Iterate through the array. Whenever a space or the end of the array is encountered, it marks the end of a word.
   • Reverse the segment of the array that represents the word (from the start index up to the character before the space).
   • Continue until all words have been reversed back to their original orientation.

We use a helper function to reverse a segment of the array in-place. This approach requires only a constant amount of extra memory (for indices and temporary variables), satisfying the O(1) space constraint.

Example Walkthrough

Let's walk through an example with s = ['t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e'].

1. Initial array:
   ['t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e']
2. After reversing the entire array:
   ['e','u','l','b',' ','s','i',' ','y','k','s',' ','e','h','t']
   (Now the words are in reverse order, but letters in each word are reversed)
3. Reverse each word one by one:
   • First word (indices 0-3): ['e','u','l','b'] → ['b','l','u','e']
   • Second word (indices 5-6): ['s','i'] → ['i','s']
   • Third word (indices 8-10): ['y','k','s'] → ['s','k','y']
   • Fourth word (indices 12-14): ['e','h','t'] → ['t','h','e']

   After all reversals, the array is:
   ['b','l','u','e',' ','i','s',' ','s','k','y',' ','t','h','e']

The words are now in reverse order, and the letters in each word are correct.

Time and Space Complexity

• Brute-force approach: Splitting the string into words and rebuilding it takes O(n) time and O(n) space, where n is the length of the string.
• Optimized in-place approach:
  • Time Complexity: O(n), since we reverse the array once (O(n)), and then reverse each word (total O(n) over all words).
  • Space Complexity: O(1), since all operations are done in-place and we only use a few variables for indices.

Summary

The key to solving the "Reverse Words in a String II" problem in-place is to use the two-step reverse technique: first reverse the whole array to get the words in the correct order, then reverse each word to restore their original spelling. This approach is both time-efficient (O(n)) and space-efficient (O(1)), making it elegant and optimal for the constraints given.

Understanding and applying in-place array manipulation is a powerful tool for many similar problems, and the reverse-in-reverse-out trick is a classic pattern worth remembering.