Reversing Words in a string

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.

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.

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.

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.