Given an input string s, reverse the order of the words. A word is a sequence of non-space characters. Words are separated by at least one space. Return a string with words in reverse order, joined by a single space (no leading/trailing spaces, no extra spaces between words).

Examples

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"

Example 3:

Input: s = "a good   example"
Output: "example good a"

Constraints

  • 1 <= s.length <= 10^4
  • s contains English letters, digits, and spaces ' '
  • There is at least one word in s

Thinking Process

Key Challenges

  1. Leading/trailing spaces – must be stripped
  2. Multiple spaces between words – must be collapsed to one
  3. Reverse word order – not character order

Approach 1: Deque (Collect Words in Reverse)

Trim leading/trailing spaces, scan left to right building words, and push each completed word to the front of a deque. This naturally reverses the order.

Approach 2: Reverse Entire String + Reverse Each Word (In-Place)

For an O(1) extra space solution:

  1. Reverse the entire string
  2. Reverse each individual word
  3. Clean up extra spaces
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Solution

class Solution {
public:
    string reverseWords(string s) {
        int left = 0, right = s.size() - 1;
        while (left <= right && s[left] == ' ') ++left;
        while (left <= right && s[right] == ' ') --right;

        deque<string> d;
        string word;
        while (left <= right) {
            if (s[left] == ' ' && !word.empty()) {
                d.push_front(word);
                word.clear();
            } else if (s[left] != ' ') {
                word += s[left];
            }
            ++left;
        }
        d.push_front(word);

        string rtn;
        while (!d.empty()) {
            rtn += d.front();
            d.pop_front();
            if (!d.empty()) rtn += " ";
        }
        return rtn;
    }
};

Solution Explanation

Approach: Opposite ends (this problem)

Key idea: ### Key Challenges

How the code works:

  1. Leading/trailing spaces – must be stripped
  2. Multiple spaces between words – must be collapsed to one
  3. Reverse word order – not character order
  4. Reverse the entire string
  5. Reverse each individual word
  6. Clean up extra spaces

Walkthrough — input s = "the sky is blue", expected output "blue is sky the":

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Comparison

Approach Time Extra Space Notes
Deque O(n) O(n) Clean, easy to understand
Reverse Twice O(n) O(1) In-place, interview follow-up

Common Mistakes

  • Not handling multiple consecutive spaces (outputting extra spaces between words)
  • Forgetting the last word (no trailing space to trigger word completion)
  • In the in-place approach: not compacting spaces during the write pass

Key Takeaways

  • “Reverse word order” has two classic approaches: collect-in-reverse (deque/stack) or reverse-entire-then-reverse-each-word
  • The in-place “reverse twice” technique is a common interview follow-up: “Can you do it in O(1) space?”
  • Trimming and compacting spaces is the fiddly part – the deque approach sidesteps it by only collecting non-empty words

References

Template Reference