Reversing Words in a string

LC75 #4

It’s day seven of doing a programming puzzle everyday and today we’re attempting LC75 #5. Here’s the problem statement

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

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

Reversing the words in a string is a classic programming exercise. But how you do it matters.

---

Method 1: The reduce() Approach

This method splits the string, reverses the array, and then uses reduce() to build the new string from scratch.

JavaScript

function reverseWordsReduce(s) {
    return s.split(" ").reverse().reduce((prev, curr) => {
        // Concatenate only if the current word is not an empty string
        if (curr) return prev + " " + curr;
        else return prev;
    }, "").trim(); // Initial value is an empty string, trim handles leading space
}

Breakdown:

1. s.split(" "): Creates an array. Importantly, consecutive spaces in the original string result in empty strings in the array. _the__sky_ becomes ['', 'the', '', 'sky', ''].

2. reverse(): Reverses the array elements in place.

3. reduce(): Iterates over the reversed array. The callback function manually concatenates each word onto an accumulator (prev), adding a space before each new word. The if (curr) check is necessary to skip the empty strings.

4. trim(): The reduce logic adds a leading space to the final string (e.g., " blue is sky the"), which trim() removes.

Analysis: This works, but it's fighting the engine. The string concatenation (prev + " " + curr) inside the reduce callback is a potential performance bottleneck. In JavaScript, strings are immutable. Each + operation doesn't modify the existing string; it creates a new string in memory. For a long string with many words, this results in many intermediate string objects that need to be created and later garbage collected.

---

Method 2: The filter() and join() Approach

This version is more declarative. It splits, reverses, cleans the array, and then joins it back together.

JavaScript

function reverseWordsJoin(s) {
    return s.split(' ').reverse().filter(x => x !== "").join(' ');
}

Breakdown:

1. s.split(' ') & reverse(): Same as the first method.

2. filter(x => x !== ""): This is the critical distinction. Instead of conditional logic inside a loop, filter creates a new, clean array containing only the actual words, discarding all empty strings in one pass.

3. join(' '): This is the key to efficiency. It takes the clean array of words (e.g., ['blue', 'is', 'sky', 'the']) and uses the highly optimized internal engine implementation to build the final string.

---

Deep Dive: Why join() Wins

Array.prototype.join() is significantly faster. It's not just a simple loop. Modern JavaScript engines like V8 implement it in low-level code (like C++), where they can pre-calculate the final string's length, allocate the required memory all at once, and then stitch the pieces together. This avoids the massive overhead of creating new strings in a loop.The performance difference lies in memory management.

• The reduce method:

  • "" (initial)

  • " blue" (creates new string)

  • " blue is" (creates another new string)

  • " blue is sky" (and another...)

  • ...and so on. This is O(M) string allocations, where M is the number of words.

• The join() method:

  1. Calculate Size: It first iterates through the array to calculate the exact final string length needed (length('blue') + length(' ') + length('is') + ...).

  2. Allocate Memory: It allocates a single memory buffer of that precise size.

  3. Copy Data: It copies each word and separator into the buffer in a single, efficient sequence.

This "calculate, allocate, copy" strategy is vastly more efficient than the repeated allocation and garbage collection churn caused by manual concatenation in a loop.

---

While both methods have a similar Big O time complexity on paper (they both must iterate over the string and the resulting array), the filter().join() method is superior.

• Performance: It leverages a native, low-level engine optimization (join()) that is purpose-built for this exact task.

• Readability: The chain of split -> reverse -> filter -> join is highly declarative. Each step describes what it is doing, making the code arguably easier to understand at a glance than the manual accumulation logic within reduce().

Don't reinvent the wheel. For building strings from array elements, join() is the correct tool for the job.