The problem. Given a string s of words separated by spaces, return the words in reverse order, joined by single spaces. s may have spaces at the start or end, and several spaces between words; the answer must have none of those.
s = "the sky is blue" -> "blue is sky the"
s = " hello world " -> "world hello"
s = "a good example" -> "example good a"The output starts with the last word, so read the string from the right. Two indexes do it: skip spaces moving left, remember where a word ends, keep moving left to where it starts, and copy that slice out. Spaces are never copied, so the extra ones vanish by themselves.
Every language can split on runs of spaces, reverse a list, and join it back. Three calls, each O(n).
function reverseWords(s) { return s.trim().split(/\s+/).reverse().join(" "); // split on runs of spaces}Time O(n), space O(n). The list of words holds a copy of every letter. In an interview, say what each built-in does and costs — some interviewers then ask you to do it by hand.
Walk i from the last character leftwards. Skip spaces; when i lands on a letter, that's a word's end. Move i left past the letters; the word is s[i+1..end]. Append it to the answer and repeat.
i walks left; each word is cut out between i + 1 and end. Try the input with extra spaces.
function reverseWords(s) { const words = []; let i = s.length - 1; while (i >= 0) { while (i >= 0 && s[i] === " ") i--; // skip spaces if (i < 0) break; const end = i; // the last letter of a word while (i >= 0 && s[i] !== " ") i--; // walk back to the space before it words.push(s.slice(i + 1, end + 1)); // the word is s[i+1..end] } return words.join(" ");}Time O(n), space O(n) for the answer. i only ever moves left, so each character is passed once; the inner loops don't restart.
Both are linear. Approach 2 is what you write when built-ins are off the table, and it shows you can handle the spaces yourself.
s.split(" ") keeps empty strings between double spaces; split on runs of spaces instead.char[]): reverse the whole array, then reverse each word back, then squeeze out extra spaces with a write pointer. Two-pointer reversal three times.