151. Reverse Words in a String II

Reversing the entire character array puts the words in the right order but spells each one backwards. A second pass that reverses each individual word (the spans between spaces) fixes the letters — all in place with O(1) extra space.

The two-reversal trick

Doing it in place with O(1) space is a two-step reversal:

1. Reverse the whole array. "the sky is blue" → "eulb si yks eht". Now the words are in the final order, but each word's letters are backwards.
2. Reverse each word. Walk the array; for each maximal run of non-space characters, reverse just that span in place → "blue is sky the".

reverse(s, 0, n-1)               # whole array
start = 0
for i in 0..n:
    if i == n or s[i] == ' ':
        reverse(s, start, i-1)   # one word
        start = i + 1

Both passes are linear and swap characters in place, so no extra array is allocated.

Worked example

"the sky is blue":

• reverse all → "eulb si yks eht"
• reverse each word → "blue is sky the".

Complexity

• Time: O(n).
• Space: O(1) — in-place character swaps.

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        reverse(chars, 0, n - 1);  // reverse the whole array
        int start = 0;
        for (int i = 0; i <= n; i++) {
            if (i == n || chars[i] == ' ') {
                reverse(chars, start, i - 1);  // reverse one word
                start = i + 1;
            }
        }
        return new String(chars);
    }

    private void reverse(char[] a, int i, int j) {
        while (i < j) {
            char t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
        }
    }
}