Reverse Words in a String II - Solution & Explanation

Problem Overview: You are given a character array representing a sentence. The goal is to reverse the order of the words in-place without allocating extra space for another string. Each word must keep its characters in the correct order while the word positions are reversed.

Approach 1: Split and Rebuild (O(n) time, O(n) space)

The most straightforward idea is to convert the character array to a string, split the string by spaces, reverse the list of words, then rebuild the sentence. This approach relies on built-in string utilities and dynamic arrays. Iterating through the words and joining them back produces the reversed sentence easily. However, it allocates additional memory proportional to the input size, which violates the in-place constraint of the problem.

Approach 2: Stack of Words (O(n) time, O(n) space)

Another option is to scan the array and push each detected word onto a stack. While iterating, track the start and end indices of each word and push them as substrings or index ranges. After the scan finishes, pop words from the stack and rewrite them back into the array with spaces between them. The stack naturally reverses word order, but it still requires O(n) auxiliary space to store the words.

Approach 3: Two-Pointer In-Place Reversal (O(n) time, O(1) space)

The optimal solution uses a two-step reversal strategy with two pointers. First, reverse the entire character array. This places the words in reverse order but also reverses the characters within each word. Next, iterate through the array and reverse each word individually using two pointers that expand from the word's boundaries. Each character is swapped at most twice, keeping the total runtime linear.

This works because reversing the whole string flips word order globally, while reversing each segment restores correct character order locally. The algorithm only swaps characters inside the same array, so the extra space stays constant. The implementation mainly involves scanning for spaces and performing in-place swaps on the segments.

The technique is a classic pattern when working with string manipulation problems where memory constraints matter. Many in-place transformations use the same "reverse whole structure, then reverse parts" trick.

Recommended for interviews: Interviewers expect the in-place two-pointer reversal. Mentioning the split-based brute force shows you understand the problem quickly, but implementing the O(n) time and O(1) space solution demonstrates stronger control of array manipulation and pointer techniques.