Reverse Words

The Problem

Given a sentence as a list of characters (a character array), reverse every individual word’s characters in-place, while keeping the words in their original order.

Input:  ['t','h','e',' ','s','k','y']
Output: ['e','h','t',' ','y','k','s']
         ↑       ↑       ↑       ↑
         "the" → "eht"   "sky" → "yks"

The words stay in place — only the characters inside each word are flipped.

Examples

Example 1

Input:  "the sky"
Output: "eht yks"

Example 2

Input:  "hello world"
Output: "olleh dlrow"

Example 3 — single word

Input:  "hello"
Output: "olleh"

Example 4 — single character words

Input:  "a b c"
Output: "a b c"   (single characters are palindromes of themselves)

Intuition

You already know how to reverse a contiguous block of characters with two pointers — that’s exactly what “Flip Characters” did. This problem asks you to apply that same operation multiple times, once per word.

The key insight: spaces act as word boundaries. Walk through the array character by character. When you find the start of a word, scan forward to find its end (the next space or the array boundary). Now you have a [word_start, word_end] range — apply the two-pointer reversal to that range. Then continue scanning for the next word.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph INPUT["Input:  't h e   s k y'"]
    direction LR
    T["t"] --- H["h"] --- E["e"] --- SP[" "] --- S["s"] --- K["k"] --- Y["y"]
  end
  subgraph W1["Word 1: indices 0-2  →  reverse 't h e'"]
    direction LR
    E2["e"] --- H2["h"] --- T2["t"] --- SP2[" "] --- S2["s"] --- K2["k"] --- Y2["y"]
  end
  subgraph W2["Word 2: indices 4-6  →  reverse 's k y'"]
    direction LR
    E3["e"] --- H3["h"] --- T3["t"] --- SP3[" "] --- Y3["y"] --- K3["k"] --- S3["s"]
  end

  INPUT -->|"reverse word 1"| W1
  W1 -->|"reverse word 2"| W2

Reverse Words on "the sky" — find each word's boundaries using a scan, then apply two-pointer reversal within that range.

Applying the Diagnostic Questions

The outer scan that finds word boundaries is bookkeeping — once a [word_start, word_end] range is identified, the inner two-pointer reversal is a textbook direct application on that sub-range.

Why find word boundaries with a linear scan instead of outer two pointers? This problem operates on each word independently, not on a single pair of positions across the whole string. The outer scan moves linearly left-to-right, identifying the next word. For each word found, two inner pointers cover it from start to end. Trying to maintain two outer pointers across the full string wouldn’t give word-by-word control — you’d lose the ability to identify where each word’s characters start and end.

What connects this to the direct-application pattern? The reverse(chars, l, r) helper is a pure direct application. The outer scan is word-boundary discovery. Reverse Words decomposes as: discover word boundary → directly apply two-pointer reversal on that range → repeat. Composing multiple direct applications, each on a different sub-range, is still the direct-application pattern — the same four checks hold for every inner reversal call.

Approach

1. Convert the string to a mutable character list (if needed)
2. Use an outer pointer i to scan from left to right
3. For each position i:
   • If chars[i] is not a space, it’s the start of a word — record word_start = i
   • Advance i until you hit a space or the end of the array — i - 1 is word_end
   • Apply two-pointer reversal on chars[word_start : word_end]
4. Return the joined result

Solution

from typing import List

class Solution:
    def reverse_words(self, s: str) -> str:
        chars = list(s)
        n = len(chars)
        i = 0

        while i < n:
            # Skip spaces between words
            if chars[i] == ' ':
                i += 1
                continue

            # Mark the start of the word
            word_start = i

            # Find the end of the word
            while i < n and chars[i] != ' ':
                i += 1
            word_end = i - 1   # last character of this word

            # Two-pointer reverse within [word_start, word_end]
            left, right = word_start, word_end
            while left < right:
                chars[left], chars[right] = chars[right], chars[left]
                left  += 1
                right -= 1

        return "".join(chars)


# --- Test ---
sol = Solution()
print(sol.reverse_words("the sky"))      # "eht yks"
print(sol.reverse_words("hello world"))  # "olleh dlrow"
print(sol.reverse_words("hello"))        # "olleh"
print(sol.reverse_words("a b c"))        # "a b c"
print(sol.reverse_words(""))             # ""

Dry Run — “hello world”

chars = ['h','e','l','l','o',' ','w','o','r','l','d']

Word 1: word_start = 0, word_end = 4

Word 2: word_start = 6, word_end = 10

Return "olleh dlrow" ✓

Complexity Analysis

Edge Cases

Key Takeaway

Reverse Words composes two ideas: scanning to find word boundaries and two-pointer reversal within a range. The outer loop handles discovery; the inner two pointers handle the work. This composition — “find a range, then operate on it with two pointers” — is a pattern that recurs throughout the two-pointer family of problems.