Log inSign up
mediumleetcodeNot Started

Reverse Words in a String

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return *a string of the words in reverse order concatenated by a single space*.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"
Explanation: Reversing word order yields "blue is sky the".

Example 2:

Input: s = " hello world "
Output: "world hello"
Explanation: Leading and trailing spaces are removed.

Example 3:

Input: s = "a good example"
Output: "example good a"
Explanation: Multiple spaces between words are reduced to a single space.

Constraints:

  • 1 <= s.length <= 104
  • s contains English letters (upper-case and lower-case), digits, and spaces ' '.
  • There is at least one word in s.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3-step reversal pattern (reverse all, reverse each word, clean spaces).
  • Compact multiple whitespace characters in-place.
  • Handle leading and trailing delimiters cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Reversing word sequences without auxiliary string splitting libraries.
  • Formatting spaced tokens with single delimiter guarantees.

Algorithmic Decision Tree:

  • Reversing word sequences without auxiliary string splitting libraries.
  • Formatting spaced tokens with single delimiter guarantees.

Connected Patterns:

Reverse Words in a String IIIReverse StringRotate Array

1. Split, Filter, Reverse, and Join

Intuition

Use built-in string splitting functions on whitespace. Discard empty tokens resulting from consecutive spaces. Reverse the array of words and join them with a single space delimiter.

When to apply: Basic high-level language built-in solution.

Algorithm

  1. Split s into tokens.
  2. Filter out empty tokens.
  3. Reverse array of tokens.
  4. Join tokens with ' '.
  5. Return result.

Split, Filter, Reverse, and Join

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [t, h, e, , s, k, y, , i, s, , b, l, u, e]
Current operationSTEP 1 OF 6
Observation: Input string contains 4 words separated by spaces
Visual state
Values and pointers at this exact step
array
S
t
h
e
s
k
y
i
s
b
l
u
e
0
↑ INPUT STRING
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Variables at this step
tokens
["the","sky","is","blue"]
wordCount
4
Check / comparison
Call s.trim().split(/\s+/): tokenize into word array.
Decision / next transition
Extracted words: ['the', 'sky', 'is', 'blue'].
Why this step matters

Observation: Input string contains 4 words separated by spaces.

Decision: Split string using whitespace delimiter into token list: ['the', 'sky', 'is', 'blue'].

Invariant: Splitting extracts intact words regardless of internal space counts.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <sstream>
5#include <algorithm>
6
7class Solution {
8public:
9 std::string reverseWords(std::string s) {
10 std::stringstream ss(s);
11 std::string word;
12 std::vector<std::string> words;
13 while (ss >> word) {
14 words.push_back(word);
15 }
16 std::reverse(words.begin(), words.end());
17 std::string res = "";
18 for (int i = 0; i < (int)words.size(); ++i) {
19 if (i > 0) res += " ";
20 res += words[i];
21 }
22 return res;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << sol.reverseWords("the sky is blue") << std::endl; // "blue is sky the"
29 std::cout << sol.reverseWords(" hello world ") << std::endl; // "world hello"
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Splits and joins N characters across memory buffers.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Two-pointer in-place whitespace compaction avoids extra string allocations.

Strict O(1) auxiliary space in mutable string environments like C++.

2. Right-to-Left Two Pointers Extraction

Intuition

Initialize j = s.length - 1. While j >= 0: skip spaces. Find the start of the word i. Extract s.substring(i + 1, j + 1) and append to result string with a space delimiter. Set j = i and repeat.

When to apply: When constructing the reversed string in a single backwards pass.

Algorithm

  1. Initialize res = "", j = s.length - 1.
  2. While j >= 0:
  3. While j >= 0 && s[j] == ' ': j--.
  4. If j < 0: break.
  5. i = j.
  6. While i >= 0 && s[i] != ' ': i--.
  7. If !res.empty(): res += ' '.
  8. res += s.substr(i + 1, j - i).
  9. j = i.
  10. Return res.

Right-to-Left Two Pointers Extraction

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [t, h, e, , s, k, y, , i, s, , b, l, u, e]
Current operationSTEP 1 OF 6
Observation: Scan from right end ($N - 1 = 14$)
Visual state
Values and pointers at this exact step
array
S
t
h
e
s
k
y
i
s
b
l
u
e
0
1
2
3
4
5
6
7
8
9
10
11
↑ i=11 ('b')
12
13
14
↑ j=14 ('e')
Variables at this step
word
blue
result
blue
i
10
Check / comparison
Scan right-to-left. Word boundaries: i=11 ('b'), j=14 ('e').
Decision / next transition
Extract word s[11..14] = 'blue'. Append to result builder.
Why this step matters

Observation: Scan from right end (N - 1 = 14). Pointer j marks word end at 14; move i left to word start at 11.

Decision: Extract substring s[11..14] = 'blue'. Add to result builder.

Invariant: Right-to-left traversal naturally yields reversed word order.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5public:
6 std::string reverseWords(std::string s) {
7 std::string res = "";
8 int j = s.size() - 1;
9 while (j >= 0) {
10 while (j >= 0 && s[j] == ' ') j--;
11 if (j < 0) break;
12 int i = j;
13 while (i >= 0 && s[i] != ' ') i--;
14 if (!res.empty()) res += " ";
15 res += s.substr(i + 1, j - i);
16 j = i;
17 }
18 return res;
19 }
20};
21
22int main() {
23 Solution sol;
24 std::cout << sol.reverseWords("the sky is blue") << std::endl; // "blue is sky the"
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N) — Visits each character at most twice in a single backwards pass.
  • Space complexity: O(N) output string

3. Three-Step In-Place Reversal (O(1) Auxiliary Space)

Intuition

1. Reverse the entire character array s[0...n-1]. 2. Loop through the reversed array: for each word, reverse its characters from start to end. 3. Clean up spaces in-place using two pointers (i, j) to remove leading/trailing and duplicate whitespace, resizing the string to the final length.

When to apply: The standard gold standard solution for in-place memory optimization.

Algorithm

  1. Reverse the entire string s.
  2. For each word separated by spaces in s, reverse the word's characters.
  3. Compact spaces: maintain write pointer i = 0. Iterate read pointer j from 0 to n - 1.
  4. - Skip leading spaces.
  5. - For each word, copy to s[i++], append single space, and skip redundant spaces.
  6. Truncate s to length i and return.

Trim, Reverse Entire String, and Reverse Word In-Place

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [t, h, e, , s, k, y, , i, s, , b, l, u, e]
Current operationSTEP 1 OF 6
Observation: Extract words while discarding leading, trailing, and multiple consecutive spaces
Visual state
Values and pointers at this exact step
array
S
the
sky
is
blue
0
↑ Original Word List
1
2
3
Variables at this step
original
the sky is blue
words
["the","sky","is","blue"]
wordCount
4
Why this step matters

Observation: Extract words while discarding leading, trailing, and multiple consecutive spaces.

Decision: Word list obtained: ["the", "sky", "is", "blue"].

Invariant: Whitespace normalization complete.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6 void cleanSpaces(std::string& s, int n) {
7 int i = 0, j = 0;
8 while (j < n) {
9 while (j < n && s[j] == ' ') j++; // skip leading spaces
10 while (j < n && s[j] != ' ') s[i++] = s[j++]; // copy word
11 while (j < n && s[j] == ' ') j++; // skip trailing spaces
12 if (j < n) s[i++] = ' '; // append single space between words
13 }
14 s.resize(i);
15 }
16public:
17 std::string reverseWords(std::string s) {
18 int n = s.size();
19 // Step 1: reverse entire string
20 std::reverse(s.begin(), s.end());
21
22 // Step 2: reverse each word
23 int start = 0, end = 0;
24 while (start < n) {
25 while (start < n && s[start] == ' ') start++;
26 end = start;
27 while (end < n && s[end] != ' ') end++;
28 std::reverse(s.begin() + start, s.begin() + end);
29 start = end;
30 }
31
32 // Step 3: clean spaces
33 cleanSpaces(s, n);
34 return s;
35 }
36};
37
38int main() {
39 Solution sol;
40 std::cout << sol.reverseWords("the sky is blue") << std::endl; // "blue is sky the"
41 std::cout << sol.reverseWords(" hello world ") << std::endl; // "world hello"
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) — Each character is reversed and shifted at most twice, using O(1) auxiliary variables.
  • Space complexity: O(1) extra space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Built-In Split, Filter, Reverse, JoinO(N)O(N)Extremely concise in Python and JavaScript.Allocates multiple intermediate string arrays.
2.Two Pointers Scanning from Right to LeftO(N)O(N)Extracts words backward directly into a single result buffer.Requires auxiliary string builder.
3.In-Place Three-Step Reversal (Optimal in C++)OptimalO(N)O(1) extra spaceTrue O(1) auxiliary space modifying characters in-place.Requires custom in-place whitespace compaction.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Leaving a trailing space after the final word in result string.

Pitfall 2:

Using naive regex split without handling multiple whitespace tokens in C++ / Java.

Crucial Edge Cases to Validate:

  • Multiple consecutive spaces between words (s = 'a b'): Compaction loop writes exactly one single space between words, returning 'b a'.
  • String with leading and trailing spaces (s = ' hello '): Leading and trailing spaces are skipped completely, returning hello.
  • Single word (s = word): Reversed twice returns identical word.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the 3-step algorithm (reverse all -> reverse words -> clean spaces) as the benchmark in-place solution.
  2. Explain how spaces are compacted with a two-pointer write/read cursor.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does reversing the entire string followed by reversing each individual word produce words in reverse order?

Back to DSA Sheet