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.
We can iterate through the character array s, using two pointers i and j to find the start and end positions of each word, then reverse each word, and finally reverse the entire character array.
The time complexity is O(n), where n is the length of the character array s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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 |
Reverse Words In A String III (LeetCode 557) | Full solution | 3 different methods • Nikhil Lohia • 20,562 views views
Watch 9 more video solutions →Practice Reverse Words in a String II with our built-in code editor and test cases.
Practice on FleetCode