Move from brute-force thinking to an efficient approach using two pointers strategy.
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"
Example 2:
Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104s contains English letters (upper-case and lower-case), digits, and spaces ' '.s.Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?
Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Two Pointers
"the sky is blue"
" hello world "
"a good example"
reverse-words-in-a-string-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #151: Reverse Words in a String
class Solution {
public String reverseWords(String s) {
List<String> words = new ArrayList<>();
int n = s.length();
for (int i = 0; i < n;) {
while (i < n && s.charAt(i) == ' ') {
++i;
}
if (i < n) {
StringBuilder t = new StringBuilder();
int j = i;
while (j < n && s.charAt(j) != ' ') {
t.append(s.charAt(j++));
}
words.add(t.toString());
i = j;
}
}
Collections.reverse(words);
return String.join(" ", words);
}
}
// Accepted solution for LeetCode #151: Reverse Words in a String
func reverseWords(s string) string {
words := []string{}
i, n := 0, len(s)
for i < n {
for i < n && s[i] == ' ' {
i++
}
if i < n {
j := i
t := []byte{}
for j < n && s[j] != ' ' {
t = append(t, s[j])
j++
}
words = append(words, string(t))
i = j
}
}
for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
words[i], words[j] = words[j], words[i]
}
return strings.Join(words, " ")
}
# Accepted solution for LeetCode #151: Reverse Words in a String
class Solution:
def reverseWords(self, s: str) -> str:
words = []
i, n = 0, len(s)
while i < n:
while i < n and s[i] == " ":
i += 1
if i < n:
j = i
while j < n and s[j] != " ":
j += 1
words.append(s[i:j])
i = j
return " ".join(words[::-1])
// Accepted solution for LeetCode #151: Reverse Words in a String
impl Solution {
pub fn reverse_words(s: String) -> String {
let mut words = Vec::new();
let s: Vec<char> = s.chars().collect();
let mut i = 0;
let n = s.len();
while i < n {
while i < n && s[i] == ' ' {
i += 1;
}
if i < n {
let mut j = i;
while j < n && s[j] != ' ' {
j += 1;
}
words.push(s[i..j].iter().collect::<String>());
i = j;
}
}
words.reverse();
words.join(" ")
}
}
// Accepted solution for LeetCode #151: Reverse Words in a String
function reverseWords(s: string): string {
const words: string[] = [];
const n = s.length;
let i = 0;
while (i < n) {
while (i < n && s[i] === ' ') {
i++;
}
if (i < n) {
let j = i;
while (j < n && s[j] !== ' ') {
j++;
}
words.push(s.slice(i, j));
i = j;
}
}
return words.reverse().join(' ');
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair of elements. The outer loop picks one element, the inner loop scans the rest. For n elements that is n × (n−1)/2 comparisons = O(n²). No extra memory — just two loop variables.
Each pointer traverses the array at most once. With two pointers moving inward (or both moving right), the total number of steps is bounded by n. Each comparison is O(1), giving O(n) overall. No auxiliary data structures are needed — just two index variables.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.