About Talks Articles

Searching using Array.prototype.reduce

4 min read

Searching for a particular element in a JavaScript array is often carried out using a typical iteration. In some cases, forEach and some can be used as well. What is often overlooked is the potential use of Array.prototype.reduce to perform such an operation.

ECMAScript 5.1 specification, in Section, describes the callback function to reduce as:

callbackfn is called with four arguments: the previousValue (or value from the previous call to callbackfn), the currentValue (value of the current element), the currentIndex, and the object being traversed.

An illustration of reduce can be seen in the following snippet. Thanks to the addition x + y, the code computes the sum of all numbers in the array, with an optional offset in the second example.

[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y });       //  15
[1, 2, 3, 4, 5].reduce(function (x, y) { return x + y }, 100);  // 115

As a matter of fact, I already covered a rather complicated construct using reduce to produce the Fibonnaci series. To perform a search using reduce, fortunately it does not need to be complicated.

Let’s take a look at the following problem (part of JavaScript Under Pressure): find the longest string in an array of strings. An imperative solution looks something like the following code (using forEach may simplify the loop but the idea remains the same):

function findLongest(entries) {
  for (var i = , longest = ''; i < entries.length; ++i) 
    if (entries[i].length > longest.length) longest = entries[i];
  return longest;

A version which relies on reduce is a single statement:

function findLongest(entries) {
  return entries.reduce(function (longest, entry) {
    return entry.length > longest.length ? entry : longest;
  }, '');


We set the initial value for longest as an empty string. The callback function for reduce ensures that longest will be kept updated because we always choose, via the convenient ternary operator, the longest string for its return value.

Now imagine that the problem is expanded, not only we need to obtain the longest string but we also need to get the index of that longest string in the array. While it sounds more complex, the solution is still as compact as before:

function findLongest(entries) {
  return entries.reduce(function (longest, entry, index) {
    return entry.length > longest.value.length ?
      { index: index, value: entry } : longest;
  }, { index: -1, value: '' });

The callback function takes advantage of the third parameter, i.e. the index of the current element. The rest is pretty much the same, except now we need to store a richer object contained both the index and the string, as opposed to just a simple string.

At this point, the problem is made even more challenging: sort the array based on the length of the string. Fortunately, this is again not as crazy as you might think. In fact, we are halfway there since we already have the ability to find the longest string in an array. This is a perfect chance to implement something like insertion sort. For every run, find the longest string, pluck it from our array, and then the push it to the result.

We can realize quickly that the loop needs to run as many as the available array elements. If you read my previous blog post on Sequence with JavaScript Array, it is obvious that we can simply use Array.apply and map for the iteration. The code will look like the following fragment. See if you can figure out the reason behind the use of splice and pop there.

entries = Array.apply(undefined, Array(entries.length)).map(function () {
  return entries.splice(findLongest(entries).index, 1).pop();

Pushing a bit to the extreme, what if the solution can only use reduce? In this case, we need to revive the trick already employed in that Fibonacci series adventure. The use of reduce is reduced (pun intended) to an accumulating iteration, we simply start with an empty array as the initial value and fill this array as we go. Inlining the longest-string-search and shortening a few variables for some additional air of mystery, the complete incantation will be as fascinating as the code below:

entries = Array.apply(undefined, Array(entries.length)).reduce(function (r) {
  return r.concat(entries.splice(
    entries.reduce(function (longest, e, i) {
      return e.length >= longest.e.length ?  { i: i, e: e } : longest;
    }, { e: '' }).i, 1
}, []);

Insertion sort is rather impractical in real-world scenarios and the above cascaded construct is not always readable. However, hopefully this can still show that Array.prototype.reduce can be quite charming at times!

Related posts:

♡ this article? Explore more articles and follow me Twitter.

Share this on Twitter Facebook

comments powered by Disqus