Reverse Word Order

The Problem

Given a string of words separated by single spaces, reverse the order of the words in-place, keeping each word’s characters intact.

Input:  "the sky is blue"
Output: "blue is sky the"

The words flip order; no word’s characters change.

Examples

Example 1

Input:  "the sky is blue"
Output: "blue is sky the"

Example 2

Input:  "hello world"
Output: "world hello"

Example 3 — single word

Input:  "hello"
Output: "hello"

Example 4

Input:  "a good example"
Output: "example good a"

Intuition

This is the hardest problem in the section, and it has a beautiful two-step trick.

If you reverse the entire string first, the words appear in reverse order — but each word’s own characters are also reversed. So in step two, you reverse each word’s characters back to normal. The two operations cancel each other out for the characters inside words, but compound their effect on word order.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  ORIG["Original string\n'the sky is blue'"]
  STEP1["Step 1: Reverse the entire string\n'eulb si yks eht'"]
  STEP2["Step 2: Reverse each individual word\n'blue is sky the'"]
  DONE(["✓  Word order reversed, characters intact"])

  ORIG -->|"two-pointer reverse full string"| STEP1
  STEP1 -->|"two-pointer reverse each word"| STEP2
  STEP2 --> DONE

The two-step trick — reversing the whole string flips word order but scrambles each word; reversing each word individually unscrambles the characters while keeping the new word order.

Why This Works — The Intuition

Let’s trace exactly what each step does to "the sky":

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph A["Original"]
    direction LR
    t["t"] --- h["h"] --- e["e"] --- sp[" "] --- s["s"] --- k["k"] --- y["y"]
  end
  subgraph B["After Step 1: reverse entire string"]
    direction LR
    y2["y"] --- k2["k"] --- s2["s"] --- sp2[" "] --- e2["e"] --- h2["h"] --- t2["t"]
  end
  subgraph C["After Step 2: reverse each word"]
    direction LR
    s3["s"] --- k3["k"] --- y3["y"] --- sp3[" "] --- t3["t"] --- h3["h"] --- e3["e"]
  end

  A -->|"reverse whole"| B
  B -->|"reverse words"| C

Step-by-step on "the sky" — after the full reverse, each word's letters are backwards; reversing each word fixes them while keeping the flipped word order.

Each word is reversed twice in total — once by the full-string reversal, once by the per-word reversal. Two reversals cancel out, returning each word’s characters to their original order. But the words themselves have moved to their new positions.

Applying the Diagnostic Questions

This is a composed direct application: two separate two-pointer passes applied in sequence. Step 1 (full reverse) is Flip Characters on the whole string. Step 2 (per-word reverse) is Reverse Words from the previous lesson. Each pass passes all four checks independently.

Why does composing two reversals give word-order reversal? Because reversing is its own inverse: reverse a sequence twice and you get back the original. For each word, the full-string reversal scrambles its characters, and the per-word reversal unscrambles them — net effect on the word’s characters: zero. But the word’s position in the string only experiences the full-string reversal (the per-word reversal doesn’t change inter-word positions, only intra-word order). So the characters come out intact, but the word slots have been rearranged. See the “Why This Works” section above for the full concrete trace.

What breaks if you only do Step 1? After reverse(0, n-1), words are in reverse order — correct — but every word’s characters are also reversed — wrong. "the sky" → "yks eht" instead of "sky the". Step 2 is what restores each word’s internal character order without disturbing the newly achieved word-order reversal.

Approach

1. Convert string to a mutable character list
2. Step 1: Reverse the entire character array with two pointers (left=0, right=n-1)
3. Step 2: Scan through the array; for each word found at range [l, r], reverse chars[l..r] with two pointers
4. Return "".join(chars)

This reuses reverse_segment(arr, l, r) from the previous lesson twice.

Solution

from typing import List

class Solution:

    def _reverse(self, chars: List[str], l: int, r: int) -> None:
        """Two-pointer reversal of chars[l..r] in-place."""
        while l < r:
            chars[l], chars[r] = chars[r], chars[l]
            l += 1
            r -= 1

    def reverse_word_order(self, s: str) -> str:
        chars = list(s)
        n     = len(chars)

        # Step 1: Reverse the entire string
        self._reverse(chars, 0, n - 1)

        # Step 2: Reverse each word individually
        i = 0
        while i < n:
            if chars[i] == ' ':
                i += 1
                continue

            word_start = i
            while i < n and chars[i] != ' ':
                i += 1
            word_end = i - 1

            self._reverse(chars, word_start, word_end)

        return "".join(chars)


# --- Test ---
sol = Solution()
print(sol.reverse_word_order("the sky is blue"))   # "blue is sky the"
print(sol.reverse_word_order("hello world"))        # "world hello"
print(sol.reverse_word_order("hello"))              # "hello"
print(sol.reverse_word_order("a good example"))     # "example good a"

Dry Run — “the sky is blue”

Step 1: Reverse entire string

"the sky is blue"
       ↓
"eulb si yks eht"

(Characters are in exact reverse order — words are backwards, characters within each word are backwards)

Step 2: Reverse each word

Final result: "blue is sky the" ✓

Complexity Analysis

Edge Cases

The Full Picture: All Six Problems

You’ve now seen every direct-application two-pointer problem in this section. They all share the same skeleton — what changes is the work done inside the loop:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  TP["Two-Pointer Direct Application"]
  FC["Flip Characters\nSwap chars from both ends"]
  PC["Palindrome Checker\nCompare chars from both ends"]
  VE["Vowel Exchange\nScan to vowel, then swap"]
  RW["Reverse Words\nApply reversal per word"]
  RS["Reverse Segments\nApply reversal per segment range"]
  RWO["Reverse Word Order\nFull reverse + per-word reverse"]

  TP --> FC
  TP --> PC
  TP --> VE
  TP --> RW
  TP --> RS
  TP --> RWO

All six direct-application problems — one template, six variations in the loop body.

Key Takeaway

Reverse Word Order is the culminating problem of this section — it composes two two-pointer operations in sequence, and it’s the first problem where the trick isn’t immediately obvious. The insight (reverse-all, then reverse-each) is a pattern worth memorising: it appears in several string manipulation problems and is a favourite in technical interviews. Once you see it, you never forget it.