Skip to main content
Talentd

Reverse Words in a String II - Solution & Explanation

MediumPremiumFree on FleetCodeTwo PointersString6 min readAsked at: Amazon, Microsoft, Uber +1
Practice this problem

Problem Statement

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 <= 105
  • s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
  • There is at least one word in s.
  • s does not contain leading or trailing spaces.
  • All the words in s are guaranteed to be separated by a single space.

Approach Overview

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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Split and Reverse WordsO(n)O(n)Quick implementation when in-place constraint does not matter
In-Place Reverse + Two PointersO(n)O(1)Preferred interview solution when modifying the array directly is required

Video Solution

LeetCode 186 - Reverse Words in a String II: A Microsoft Journey • The Lofi Dev • 2,233 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Reverse Words in a String II easy or hard?
Reverse Words in a String II is generally rated Medium difficulty. The logic is simple conceptually but requires careful index handling to reverse the array and then reverse each word without using extra memory.
Reverse Words in a String II Python/Java solution
Python, Java, C++, Go, and TypeScript solutions typically implement the same pattern: reverse the entire array, then scan for spaces and reverse each word segment. Languages differ slightly in how character arrays are handled, but the core two-pointer swapping logic remains identical.
How to solve Reverse Words in a String II in O(n)?
Reverse the whole character array first so the word order becomes reversed. Then iterate through the array to detect word boundaries separated by spaces and reverse each word segment using two pointers. Each character is swapped at most twice, giving O(n) time complexity and constant extra space.
What is the best approach for Reverse Words in a String II?
The best approach uses an in-place two pointers technique. First reverse the entire character array, then iterate through the array and reverse each word individually. This keeps the words in reversed order while restoring each word's characters. The algorithm runs in O(n) time with O(1) extra space.
Is Reverse Words in a String II asked at Google/Amazon/Meta?
Reverse Words in a String II appears in interviews at companies that test string manipulation and in-place array operations, including large tech companies like Amazon, Meta, and Google. Interviewers use it to evaluate pointer manipulation, edge case handling, and understanding of in-place algorithms.
What data structure is used in Reverse Words in a String II?
The problem operates directly on a character array. The algorithm mainly relies on the two pointers technique to reverse segments of the array. No additional data structures are required for the optimal O(1) space solution.
What is the time complexity of Reverse Words in a String II?
The optimal solution runs in O(n) time because every character is visited a constant number of times. One pass reverses the entire array and another pass reverses each word segment. The space complexity is O(1) since the operation is done directly on the input array.

Ready to solve this problem?

Practice Reverse Words in a String II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reverse Words in a String

Next

Rotate Array