Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 4

In-Place String Reversal: Words

Recommended resources

Introduction

Building on our mastery of in-place reversal for entire arrays and specific segments, we now turn to a classic problem that requires a more strategic application of this skill. This lesson addresses how to reverse the order of words within a string, such as transforming "the sky is blue" into "blue is sky the", with the critical constraint of using only constant, or O(1), extra space.

This constraint immediately rules out simpler approaches like splitting the string into a list of words, reversing the list, and rejoining it, as that would require O(N) space. Instead, we'll explore an elegant two-pass algorithm that achieves the result by cleverly applying the segment reversal technique you've already practiced. This pattern is the key to solving LeetCode problem 186, "Reverse Words in a String II," which is on your target list.

The Two-Pass Reversal Strategy

The problem might seem complex to solve in-place, but a non-obvious, two-step trick makes it surprisingly manageable. The core idea is to first reverse the entire character array, and then go back and reverse each individual word.

Let's trace this with an example: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

  1. Step 1: Reverse the entire array.
    Applying our standard two-pointer reversal to the whole array gives us:
    ["e","u","l","b"," ","s","i"," ","y","k","s"," ","e","h","t"]

    Notice what this accomplished: the words are now in the correct final order (blue, is, sky, the), but each word itself is spelled backward.

  2. Step 2: Reverse each individual word.
    Now, we iterate through the array, identify the boundaries of each (now-backward) word, and apply our segment reversal function to each one.

    • Reverse "eulb" -> "blue"
    • Reverse "si" -> "is"
    • Reverse "yks" -> "sky"
    • Reverse "eht" -> "the"

The final array becomes ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"], which is the desired output.

This article from NeetCode provides a concise explanation of this exact intuition.

Solutions

This resource clearly describes the two-pass algorithm. As you read, focus on how the initial global reversal sets up the problem for the second pass of local, per-word reversals.

Read the section from Intuition and Algorithm. This text solidifies the two-step logic we just discussed.

Implementation and Execution

To implement this, we can reuse the reverse helper function that you are already familiar with, which reverses a segment of an array given start and end indices. The main logic will then orchestrate the two passes: one call to reverse for the entire array, followed by a loop that finds and reverses each word.

The trickiest part of the second pass is correctly identifying word boundaries. A common approach is to use two pointers, start and end, to scan the array. start marks the beginning of the current word, and end iterates forward until it finds a space. Once a space is found at index end, we know a word exists in the segment from start to end - 1, which we can then reverse.

A crucial edge case is handling the very last word, as it isn't followed by a space. The loop must account for this to ensure the last word is also reversed.

The following Python code from the NeetCode resource provides a very clean and modular implementation of this strategy.

Solutions

This resource presents a Python solution that neatly separates the logic into helper functions, making the code readable and reusable. It also confirms the efficiency of this approach.

First, examine the Python code. Notice how it defines a reverse helper and a reverse_each_word helper. The main reverseWords function is simply a composition of these two steps. Pay attention to how the reverse_each_word function uses a while loop to find the end of each word. After reviewing the code, read the brief complexity analysis that follows. It confirms that the algorithm runs in O(N) time and, critically, O(1) space.

Walkthrough and Common Pitfalls

While the logic is straightforward once you see it, implementation can be prone to off-by-one errors or missed edge cases. Walking through a concrete example and being aware of common mistakes is essential.

The AlgoMonster resource provides an excellent, detailed walkthrough and a discussion of frequent pitfalls. Interestingly, it presents the algorithm in the reverse order: first reversing each word, then reversing the entire array. As you might deduce, the outcome is the same, but the walkthrough is valuable regardless of the order.

186. Reverse Words in a String II - In-Depth Explanation

This article will help you solidify your understanding by tracing the algorithm's execution and highlighting potential errors to avoid.

Start by reading the Example Walkthrough for the input ['c','a','t',' ','i','s']. Follow each step of the transformation carefully. Next, review the section on Common Pitfalls. Pay special attention to the first two points: "Forgetting to Handle the Last Word" and "Incorrect Boundary Indices When Reversing." These are the most common bugs when implementing this pattern from scratch.

Conclusion

In this lesson, you've learned a powerful and efficient in-place algorithm for reversing the order of words in a string. This technique is a prime example of how combining simple, fundamental operations—in this case, segment reversal—can solve more complex problems.

The key takeaways are:

  • The Two-Pass Strategy: The reverse-all-then-reverse-each pattern is the canonical O(1) space solution for this problem.
  • Building on Primitives: The algorithm's elegance comes from reusing the same reverse_segment function for both the global and local reversals.
  • Boundary and Edge Case Handling: Success hinges on correctly identifying word boundaries and ensuring the last word is not missed.

In our next lesson, we will continue exploring in-place string manipulations by tackling a related problem: reversing only the prefix of a string up to the first occurrence of a specific character. This will further refine your ability to apply reversal techniques with dynamic boundaries.