LeetCode 151: Reverse Words in a String in Go

The problem that looks simple until the whitespace shows up

You open LeetCode 151 — Reverse Words in a String expecting a variation on reversing a string, and mostly, that's right. Given "the sky is blue", you need "blue is sky the", the words reverse order, not the letters inside them.

Then you notice the real complication buried in the constraints: the input can have leading spaces, trailing spaces, and multiple spaces between words (" the sky is blue "), and none of that garbage is allowed to survive into your output.

So this problem is really two problems stacked together: reversing word order, and cleaning up whitespace. This post walks through two ways to solve it in Go, and along the way clears up a common misconception about what "O(1) extra space" actually means once your language doesn't let you mutate strings directly.

Approach 1: split, reverse, join

The simplest mental model: let the standard library handle the messy whitespace work, then reuse the same two-pointer swap pattern from reversing vowels, one level up, swapping whole words instead of characters.

Step 1: Split, with whitespace handled for free

words := strings.Fields(s)

strings.Fields splits on any run of whitespace and silently discards empty pieces. That one call solves leading spaces, trailing spaces, and multiple spaces between words, all at once:

strings.Fields("  the sky  is blue  ")
// → []string{"the", "sky", "is", "blue"}

Compare that to strings.Split(s, " "), which would instead give you ["", "", "the", "sky", "", "is", "blue", "", ""]; every extra space becomes an empty string you'd have to filter out yourself. Picking the right stdlib function does half the problem for you here.

Step 2: Reverse the slice of words

Same collision two-pointer pattern as before, left and right start at opposite ends and swap toward the middle. The only difference from reversing vowels is that every element gets swapped unconditionally; there's no "is this a vowel" check gating the swap:

left, right := 0, len(words)-1
for left < right {
    words[left], words[right] = words[right], words[left]
    left++
    right--
}

Step 3: Join back with single spaces

strings.Join(words, " ")

Full Solution

func reverseWords(s string) string {
    words := strings.Fields(s)

    left, right := 0, len(words)-1
    for left < right {
        words[left], words[right] = words[right], words[left]
        left++
        right--
    }

    return strings.Join(words, " ")
}

Trace

" the sky is blue "

1. strings.Fields → ["the", "sky", "is", "blue"]

2. Reverse → ["blue", "is", "sky", "the"]

3. strings.Join → "blue is sky the" ✅

Three lines of real logic, and every whitespace edge case handled without writing a single line for it. The cost: strings.Fields allocates a slice of strings (one per word), and strings.Join allocates another buffer for the final result. Fine for most purposes, but not the leanest possible solution, which is exactly what Approach 2 addresses.

Approach 2: reverse-then-reverse, in place

This is the classic interview follow-up answer: reverse the entire string first, then reverse each word individually back to normal. It reuses an idea worth remembering, since it reappears in other problems too: reverse the whole thing, then reverse the parts.

Why "reverse, then reverse" works

Take "the sky". Reverse it completely, character by character:

"the sky" → "yks eht"

The word order is now correct (sky's letters come first, then the's), but each word's internal letter order got scrambled as a side effect of reversing everything at once. So a second pass fixes just that: scan for each word's boundaries and reverse only that sub-range, back to normal:

"yks eht" → "sky eht" → "sky the"

Result: "sky the"; word order fixed by the full reversal, letters fixed locally afterward, without disturbing the word order that's already correct.

The part that's actually new: whitespace compaction, in place

Since we can't call strings.Fields here without giving up the "in place" goal, whitespace has to be compacted manually, using a pattern we haven't needed until now: the read/write pointer technique (two pointers moving in the same direction, at different speeds, as opposed to the collision pattern, which moves them toward each other).

Think of it like re-typing a messy sentence onto the same sheet of paper, one pen, no extra paper. You read through with one pointer; every time you find something worth keeping, you write it at the next available spot with a second pointer, which is always at or behind where you're reading, so you never overwrite something you still need.

write := 0
read := 0
for read < n {
    for read < n && b[read] == ' ' {
        read++ // skip spaces entirely
    }
    if read == n {
        break // trailing spaces exhausted
    }
    if write != 0 {
        b[write] = ' ' // exactly one separator, except before the first word
        write++
    }
    for read < n && b[read] != ' ' {
        b[write] = b[read] // copy the word
        write++
        read++
    }
}
b = b[:write]
n = write

Why this collapses multiple spaces into one: the inner "skip spaces" loop consumes an entire run of spaces before write ever moves; one space or ten, doesn't matter. Why it drops leading/trailing spaces: the separator is only written if write != 0, so nothing goes in before the first word, and once the last word is copied, there's no new word left to trigger writing a trailing separator.

Reverse the whole compacted string

reverse(b, 0, n-1)

using a small unconditional helper:

func reverse(b []byte, left, right int) {
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

Reverse each word back to normal

start := 0
for i := 0; i <= n; i++ {
    if i == n || b[i] == ' ' {
        reverse(b, start, i-1)
        start = i + 1
    }
}

The loop runs to i <= n, one past the last index, specifically so the final word, which has no trailing space to mark its end, still gets caught and reversed.

Full Solution

func reverseWords(s string) string {
    b := []byte(s)
    n := len(b)

    write := 0
    read := 0
    for read < n {
        for read < n && b[read] == ' ' {
            read++
        }
        if read == n {
            break
        }
        if write != 0 {
            b[write] = ' '
            write++
        }
        for read < n && b[read] != ' ' {
            b[write] = b[read]
            write++
            read++
        }
    }
    b = b[:write]
    n = write

    reverse(b, 0, n-1)

    start := 0
    for i := 0; i <= n; i++ {
        if i == n || b[i] == ' ' {
            reverse(b, start, i-1)
            start = i + 1
        }
    }

    return string(b)
}

func reverse(b []byte, left, right int) {
    for left < right {
        b[left], b[right] = b[right], b[left]
        left++
        right--
    }
}

Three passes, three applications of the same two-pointer family: read/write for compaction, collision for the full reversal, collision again (on sub-ranges) for the per-word fix.

What "extra space" (auxiliary space) means

When people analyze space complexity, they usually split memory usage into two buckets:

• Input space: memory used to store the input itself (the string you were given). This doesn't count against you; you didn't choose to receive a big input.

• Extra / auxiliary space: any additional memory your algorithm allocates beyond the input, in order to compute the answer.

"O(1) extra space" means: no matter how large the input n gets, the amount of additional memory your algorithm needs stays constant; a fixed handful of variables (a few ints for pointers/indices, maybe one temp variable), and nothing that grows with n.

What "truly O(1)" looks like, concretely

Take the classic version of this problem in C or C++, where a string is literally a mutable array of characters (char[] or char*) sitting in memory that you already own.

In that world, the reverse-then-reverse-words algorithm works like this:

1. You're handed the character array directly; this is your input space, already allocated.

2. You do the whitespace compaction, the full reversal, and the per-word reversal directly inside that same array, using only a few integer index variables (read, write, left, right, start).

3. When you're done, that same array, now holding the answer, is returned or printed; no new array was ever created.

The only extra memory used across the entire algorithm is a small, fixed number of integers; regardless of whether the string is 10 characters or 10 million. That's genuinely O(1) extra space: the auxiliary memory footprint never grows with n.

So which one is actually "O(1) extra space"? Neither, really, and here's why that matters

This is worth being precise about, because "O(1) space" gets thrown around loosely.

"Extra" or "auxiliary" space means memory used beyond the input itself; a fixed handful of index variables counts as O(1) extra space; anything that grows with the input size n doesn't.

In C or C++, a string is a mutable char[] you already own. The reverse-then-reverse algorithm edits that array directly and hands the same array back; no new array is ever created. The only extra memory used is a few integers (read, write, left, right), regardless of whether the string is 10 characters or 10 million. That's genuinely O(1) extra space.

Go doesn't let you do that, because string is immutable by design (this exists so that substrings can safely share underlying memory without one mutation corrupting another). So:

b := []byte(s)      // copies the input, O(n) new memory, before any logic runs
// ... in-place work on b ...
return string(b)    // copies again, another O(n) new memory

Both of those copies are proportional to n. So strictly speaking, Approach 2's Go implementation is O(n) extra space overall, not O(1), the in-place logic between those two conversions is O(1) extra beyond the []byte copy, but the copy itself isn't optional in Go.

Then what's actually different between the two approaches?

Since neither is truly O(1) in Go, the real distinction is in how much intermediate garbage gets created along the way, constant factors that big-O notation deliberately hides but that matter in practice:

So when this problem's classic follow-up asks "can you do it with O(1) extra space," the honest answer in Go is: not truly, since string immutability forces at least one input-sized copy in and one out;

but Approach 2 is still the intended and meaningfully leaner answer, because it avoids all the additional per-word allocations Approach 1 introduces on top of that unavoidable baseline.

Summary

• Approach 1 (strings.Fields → reverse slice → strings.Join) is the simplest correct solution: whitespace cleanup comes free from the standard library, and the reversal is the same collision two-pointer pattern from earlier problems, just applied to whole words.

• Approach 2 (compact → reverse all → reverse each word) is the leaner, interview-favorite solution, introducing the read/write pointer pattern for in-place compaction alongside the familiar collision pattern for reversal; two flavors of "two pointers," composed across three passes.

• "O(1) extra space" is baseline-dependent. In C/C++, it means genuinely no new allocations. In Go, string immutability forces an input-sized copy in and out regardless of approach, so the honest framing is: Approach 2 minimizes allocations beyond that unavoidable baseline, rather than achieving true O(1).

That last point is the one worth carrying forward to every future string problem in Go: read space-complexity claims with the question "O(1) relative to what baseline?" in mind, especially in a language where the built-in string type won't let you mutate in place at all.

Let's connect!

One of the best parts of writing in public is the people you meet along the way, engineers at different stages of their journey, working on similar problems from completely different angles.

If something in this post resonated, if you spotted a bug, or if you just want to talk Go, Kubernetes, Platform Engineering, DevOps, or whatever, I'm always happy to hear from you.

• LinkedIn

• GitHub

• Twitter / X

Building from Asunción, Paraguay 🇵🇾