Watch 10 video solutions for Reverse Words in a String II, a medium level problem involving Two Pointers, String. This walkthrough by Knowledge Center has 201,648 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a character array 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 a single space.
Your code must solve the problem in-place, i.e. without allocating extra space.
Example 1:
Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"] Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Example 2:
Input: s = ["a"] Output: ["a"]
Constraints:
1 <= s.length <= 105s[i] is an English letter (uppercase or lowercase), digit, or space ' '.s.s does not contain leading or trailing spaces.s are guaranteed to be separated by a single space.Problem Overview: You are given a character array representing a sentence. Reverse the order of words in-place without allocating extra memory. Words are separated by spaces, and the characters of each word must remain in correct order after the transformation.
Approach 1: Split and Rebuild (O(n) time, O(n) space)
The most straightforward solution converts the character array into a string, splits it by spaces, reverses the word list, and joins it back. Each word stays intact while the order of words flips. This works well in languages with convenient string utilities, but it violates the in-place constraint because a new list of words and a new string are created. Time complexity is O(n) since each character is processed once, and space complexity is O(n) due to the extra storage for the split words.
Approach 2: In-Place Reverse with Two Pointers (O(n) time, O(1) space)
The optimal strategy uses the two pointers technique on the string array. First, reverse the entire character array. This places the words in the correct reversed order but also reverses each word's characters. Next, scan the array and reverse each individual word using two pointers that expand from the word's boundaries. Each character participates in at most two swaps: one during the full reversal and one during the word-level reversal. This guarantees O(n) time complexity with O(1) extra space.
Recommended for interviews: The in-place two-pointer method is what interviewers expect. It demonstrates control over array manipulation and pointer boundaries while maintaining constant extra space. Mentioning the split-and-rebuild approach shows baseline understanding, but implementing the in-place reversal proves you can optimize both memory usage and runtime.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Reverse Words | O(n) | O(n) | Quick implementation when in-place constraint does not matter |
| In-Place Reverse + Two Pointers | O(n) | O(1) | Preferred interview solution when modifying the array directly is required |