LeetCode 186: Reverse Words in a String II Solution in Python Explained

Problem Statement

In LeetCode 186, you’re given a character array s (e.g., ["t","h","e"," ","s","k","y"]) and its length. Your task is to reverse the order of words in-place, modifying s so that words appear in reverse order while each word’s characters remain in their original order (e.g., ["t","h","e"," ","s","k","y"] becomes ["s","k","y"," ","t","h","e"]). You must use O(1) extra space, not counting the input array. This builds on LeetCode 151: Reverse Words in a String, adding the in-place constraint, and differs from SQL queries like LeetCode 185: Department Top Three Salaries.

Constraints

• 1 <= s.length <= 10^5
• s[i] is a printable ASCII character.
• Words are separated by single spaces, no leading/trailing spaces.
• O(1) extra space required.

Example

Let’s see some cases:

Copy codeInput: s = ["t","h","e"," ","s","k","y"]
Output: ["s","k","y"," ","t","h","e"]
Explanation: "the sky" → "sky the".

Copy codeInput: s = ["h","e","l","l","o"]
Output: ["h","e","l","l","o"]
Explanation: Single word, no change.

Copy codeInput: s = ["a"," ","b"]
Output: ["b"," ","a"]
Explanation: "a b" → "b a".

These examples show we’re reversing word order in-place.

Understanding the Problem

How do you solve LeetCode 186: Reverse Words in a String II in Python? Take s = ["t","h","e"," ","s","k","y"]. We need to transform it into ["s","k","y"," ","t","h","e"] without using extra arrays beyond O(1) space. Splitting and joining isn’t allowed (O(n) space), so we must manipulate the array in-place. The solution involves reversing the entire array, then reversing each word individually, all while tracking word boundaries. This isn’t an SQL task like LeetCode 184: Department Highest Salary; it’s about in-place string manipulation. We’ll use: 1. Two-Pointer In-Place Reversal: O(n) time, O(1) space—our best solution. 2. Array Split and Reverse: O(n) time, O(n) space—an alternative (not strictly compliant).

Let’s dive into the best solution.

Best Solution: Two-Pointer In-Place Reversal Approach

Explanation

Two-Pointer In-Place Reversal reverses words in-place by:

• Reversing the entire array to flip word order.
• Using two pointers to identify and reverse each word back to its original order.
• Modifying s directly with O(1) extra space.

Steps: 1. Reverse all characters (e.g., "the sky" → "yks eht"). 2. Iterate with pointers to find word boundaries (spaces), reversing each word (e.g., "sky the").

This achieves O(n) time (two passes), O(1) space (few variables), and meets the in-place requirement efficiently.

For ["t","h","e"," ","s","k","y"]:

• Reverse all: ["y","k","s"," ","e","h","t"].
• Reverse words: ["s","k","y"," ","t","h","e"].

Step-by-Step Example

Example 1: s = ["t","h","e"," ","s","k","y"]

Goal: Modify s to ["s","k","y"," ","t","h","e"].

• Step 1: Reverse entire array.
• ["t","h","e"," ","s","k","y"] → ["y","k","s"," ","e","h","t"].
• Step 2: Identify and reverse words.
• Start=0, end=2 (before space): ["y","k","s"] → ["s","k","y"].
• Start=4, end=6: ["e","h","t"] → ["t","h","e"].
• s = ["s","k","y"," ","t","h","e"].
• Finish: s is modified in-place.

Example 2: s = ["h","e","l","l","o"]

Goal: No change (single word).

• Step 1: Reverse all.
• ["h","e","l","l","o"] → ["o","l","l","e","h"].
• Step 2: Reverse word (no spaces).
• Start=0, end=4: ["o","l","l","e","h"] → ["h","e","l","l","o"].
• Finish: s = ["h","e","l","l","o"].

Example 3: s = ["a"," ","b"]

Goal: Modify s to ["b"," ","a"].

• Step 1: Reverse all.
• ["a"," ","b"] → ["b"," ","a"].
• Step 2: Reverse words.
• Start=0, end=0: ["b"].
• Start=2, end=2: ["a"].
• s = ["b"," ","a"].
• Finish: s is modified in-place.

How the Code Works (Two-Pointer In-Place Reversal) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef reverseWords(s: list[str]) -> None:
    # Line 1: Reverse helper function
    def reverse(arr: list[str], start: int, end: int) -> None:
        # Reverse subarray from start to end (e.g., "the" to "eht")
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            # Swap characters (e.g., t↔e)
            start += 1
            end -= 1

    # Line 2: Reverse entire array
    reverse(s, 0, len(s) - 1)
    # Full reversal (e.g., "the sky" → "yks eht")

    # Line 3: Initialize pointers
    start = 0
    # Word start (e.g., 0)
    for i in range(len(s)):
        # Iterate array (e.g., 0 to 6)

        # Line 4: Find word end and reverse
        if s[i] == " ":
            # Space found (e.g., i=3)
            reverse(s, start, i - 1)
            # Reverse word (e.g., "yks" → "sky")
            start = i + 1
            # Next word start (e.g., 4)
        elif i == len(s) - 1:
            # End of array (e.g., i=6)
            reverse(s, start, i)
            # Reverse last word (e.g., "eht" → "the")

    # No return, s modified in-place

This detailed breakdown clarifies how two-pointer in-place reversal efficiently reverses words.

Alternative: Array Split and Reverse Approach

Explanation

Array Split and Reverse splits and reverses words (not O(1) space):

• Join s into a string, split into words.
• Reverse the word list.
• Join back into a string, convert to char array.
• Copy back to s.

It’s a practical alternative, O(n) time, O(n) space (violates O(1) constraint), but simpler conceptually, included for contrast despite not meeting the problem’s strict requirement.

For ["t","h","e"," ","s","k","y"]:

• Split: ["the", "sky"].
• Reverse: ["sky", "the"].
• Join: "sky the" → ["s","k","y"," ","t","h","e"].

Step-by-Step Example (Alternative)

For the same example:

• Step 1: Join and split.
• "the sky" → ["the", "sky"].
• Step 2: Reverse words.
• ["sky", "the"].
• Step 3: Join and convert.
• "sky the" → ["s","k","y"," ","t","h","e"].
• Step 4: Copy to s.
• Finish: s = ["s","k","y"," ","t","h","e"].

How the Code Works (Array Split)

Copy codedef reverseWordsSplit(s: list[str]) -> None:
    # Uses O(n) space, not compliant
    string = ''.join(s)
    words = string.split()
    words.reverse()
    result = list(' '.join(words))
    for i in range(len(s)):
        s[i] = result[i]

Complexity

• Two-Pointer In-Place Reversal:
• Time: O(n) – two passes.
• Space: O(1) – constant space.
• Array Split and Reverse:
• Time: O(n) – split, reverse, join.
• Space: O(n) – word list and string (not compliant).

Efficiency Notes

Two-Pointer In-Place Reversal is the best solution with O(n) time and O(1) space, meeting the problem’s strict requirement—Array Split and Reverse uses O(n) space, violating the constraint, but is simpler, included for educational contrast despite not being a valid solution per the problem’s rules.

Key Insights

• In-Place: Two-step reversal.
• Split: Space-intensive shortcut.
• Words: Space-separated.

Additional Example

For s = ["a","b","c"," ","d"]:

• Goal: ["d"," ","a","b","c"].
• In-Place: Reverse all → "d cba", reverse words → "d abc".

Edge Cases

• Single Word: No change.
• Two Words: Simple swap.
• All Spaces: No words, unchanged.

Both handle these, but split uses extra space.

Final Thoughts

LeetCode 186: Reverse Words in a String II in Python is a clever in-place challenge. The Two-Pointer In-Place Reversal solution excels with its efficiency and compliance, while Array Split and Reverse offers a simpler (non-compliant) approach. Want more? Try LeetCode 151: Reverse Words in a String for the O(n) space version or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 186 on LeetCode with ["t","h","e"," ","s","k","y"], aiming for ["s","k","y"," ","t","h","e"]—test your skills now!