Reverse Words in a String II

medium string two pointers in-place

Problem

Given a character array s, reverse the order of the words in place. A word is a maximal run of non-space characters; words are separated by a single space and the array contains no leading or trailing spaces.

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

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

Reverse the whole array → "eulb si yks eht", then reverse each word in place → "blue is sky the".

sentence

def reverse_words(s):
    def reverse(l, r):
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 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

function reverseWords(s) {
  function reverse(l, r) {
    while (l < r) {
      [s[l], s[r]] = [s[r], s[l]];
      l++;
      r--;
    }
  }
  const n = s.length;
  reverse(0, n - 1);
  let start = 0;
  for (let i = 0; i <= n; i++) {
    if (i === n || s[i] === " ") {
      reverse(start, i - 1);
      start = i + 1;
    }
  }
}

class Solution {
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        int start = 0;
        for (int i = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    private void reverse(char[] s, int l, int r) {
        while (l < r) {
            char tmp = s[l]; s[l] = s[r]; s[r] = tmp;
            l++; r--;
        }
    }
}

void reverseWords(vector<char>& s) {
    auto rev = [&](int l, int r) {
        while (l < r) { swap(s[l], s[r]); l++; r--; }
    };
    int n = s.size();
    rev(0, n - 1);
    int start = 0;
    for (int i = 0; i <= n; i++) {
        if (i == n || s[i] == ' ') {
            rev(start, i - 1);
            start = i + 1;
        }
    }
}

Explanation

Reversing the order of words in place becomes easy with a two-step trick: reverse the whole array, then reverse each word back individually.

Why does this work? Reversing everything flips both the word order and the letters inside each word. The word order is now correct, but each word is spelled backwards. Reversing each word a second time fixes the spelling while keeping the new word order.

Both reversals use the same reverse(l, r) helper — the standard two-pointer swap from the ends inward. To find words in the second phase, we scan for spaces (and the end of the array), reversing the segment from start to i - 1 each time we hit a boundary.

It is all in place with O(1) extra space, and every character is swapped a constant number of times, so it stays linear.

Example: "the sky is blue". Full reverse → "eulb si yks eht". Reverse each word → "blue is sky the".

Time: O(n) Space: O(1)