Given a string, return its words in reverse order, separated by single spaces, with no leading or trailing spaces.
Before you code
" ".join(reversed(s.split())) solves it in one line and O(n) extra space. The interesting version works on a mutable array of characters with O(1) extra space, which is how you would do it in C.
Hints
- First compact the spaces with a read and a write index: copy words across, and write a single space between them.
- Reverse the whole compacted array with two indexes from the ends.
- Then reverse each word back, by finding each word's start and end and reversing that range.
- Each character is touched a constant number of times, so the total is O(n).
Production & complexity notes
When solving Reverse words in a string on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Two pointers on arrays to reinforce the underlying pattern.
What it practices
Combining in-place reversal and compaction, from Two pointers on arrays.