Generated by Codex with GPT-5

Difficulty: MEDIUM
Problem: Reverse Words in a String

Problem gist

The input is a string that contains words separated by spaces. The output should contain the same words in reverse order, with exactly one space between adjacent words and no leading or trailing spaces.

The important detail is that the function is not reversing letters inside each word. It is reversing the sequence of words. For example, the words ["the", "sky", "is", "blue"] become ["blue", "is", "sky", "the"].

Extra spaces are noise. Multiple spaces between words, leading spaces, and trailing spaces all collapse away in the final answer.

Deriving the optimal solution

Every correct solution must inspect the string at least once, because any character could be part of a word or a separator. That gives a natural lower bound of O(n) time.

Once that is clear, the simplest optimal plan is:

1. Scan the input from left to right and extract real words, skipping runs of spaces.
2. Reverse the list of extracted words.
3. Join the words with a single space.

This works because the output only cares about word order and normalized spacing. Once the words have been separated from the spaces, the original spacing no longer carries useful information.

Python’s s.split() and " ".join(reversed(...)) express the same idea compactly. In an interview, though, it is useful to be able to implement the word extraction directly. That shows exactly how extra spaces are ignored and avoids leaning on a library method for the core parsing behavior.

Python solution

from typing import List


class Solution:
    def reverseWords(self, s: str) -> str:
        """Return the words of s in reverse order with normalized spacing."""
        words = self._extract_words(s)
        words.reverse()
        return " ".join(words)

    def _extract_words(self, text: str) -> List[str]:
        words: List[str] = []
        index = 0
        length = len(text)

        while index < length:
            # Ignore leading spaces and repeated spaces between words.
            while index < length and text[index] == " ":
                index += 1

            if index == length:
                break

            word_start = index
            while index < length and text[index] != " ":
                index += 1

            words.append(text[word_start:index])

        return words

The scan touches each character at most a constant number of times, so the time complexity is O(n). The extra space is O(n) for the extracted words and the returned string. In Python, this is the practical optimal space bound because strings are immutable and the answer itself must be newly constructed.

Interview follow-ups

Can this be done in place if the input is a mutable character array?

Yes. If the input is a mutable array of characters rather than an immutable Python string, the classic in-place approach is to first normalize spaces, then reverse the entire character array, then reverse each individual word.

Normalizing spaces removes leading spaces, trailing spaces, and duplicate spaces between words while compacting the useful characters toward the front. Reversing the entire array puts the words in the desired order, but it also reverses the letters inside each word. A final pass over the word boundaries fixes that by reversing each word back to normal.

This approach still takes O(n) time. Its extra working space can be O(1) beyond the mutable array, although the output length may shrink when extra spaces are removed.

What if the interviewer allows Python built-ins?

Then the idiomatic solution is " ".join(reversed(s.split())). The split() call without arguments treats consecutive whitespace as one separator and drops leading or trailing whitespace, which is exactly the normalization this problem needs.

This is still an O(n) solution because Python must scan the input to find the words and then build the output string. The tradeoff is that it hides the parsing details. That is fine for production code, but in an interview the manual scan is often better evidence that the candidate understands the edge cases.

What if the input is extremely large?

If the full string fits in memory, the same O(n) scan is still the right algorithm. The main concern becomes avoiding unnecessary copies. A manual scanner can collect word ranges first, then write words into an output buffer in reverse order, which avoids storing separate word strings before the final output is built.

If the input is a true stream and cannot be stored, reversing all words exactly requires keeping enough information to emit the last word first. That means the algorithm still needs O(n) storage in the worst case, either in memory or in external storage. The reason is fundamental: the first output word is not known until the end of the input has been read.

How should tabs, newlines, or Unicode whitespace be handled?

The LeetCode version describes spaces, so checking text[index] == " " is enough for that contract. If the product requirement says any whitespace should separate words, the scanner should use text[index].isspace() or delegate to Python’s default split() behavior.

That changes the parsing rule but not the algorithm. The scan still extracts maximal word runs, reverses their order, and joins them with the required separator. The main tradeoff is that Unicode-aware whitespace handling can be broader than expected, so production code should match the exact input contract instead of guessing.

What if the output must preserve the original spacing inside the string?

That becomes a different problem. The original LeetCode task explicitly normalizes spaces, so spaces are separators rather than data to preserve. If spacing must be preserved, the solution has to define whether spaces stay attached to the word before them, the word after them, or their original character positions.

Once that rule is clear, the implementation can tokenize both word runs and space runs, then rearrange the word tokens while placing the space tokens according to the chosen contract. The complexity remains O(n), but the edge cases become more subtle because whitespace is now part of the output semantics.

Takeaway

The key move is to separate words from separators. After the real words are extracted, the problem reduces to reversing a list and joining it with one space. That gives the optimal O(n) time solution, handles messy spacing cleanly, and leaves room to discuss in-place character-array variants when the input model changes.