Are one-liners always the best solutions?

Whenever I solved an algorithm on leetcode or codesignal, I liked to look at others solutions. For Codesignal in particular, a lot of the top voted solutions were one-liners. I loved looking at these clever solutions which seemed to both simplify the problem while also introducing sometimes complex answers.

This week, I encountered an opportunity to introduce my own one-liner solution. Unfortunately, it didn’t turn out how I wanted it to.

The Problem

Given an array of integers such as [1, 2, 2, 4, 4, 4] return the number of occurrences of the largest value. Since four shows up three times in this array, the answer would be 3.

One liner solution

After playing around with a few for-loop type solutions, it occurred to me that I could use Math.max to find the largest value.

Math.max(array)

However, this returned an error. I soon remembered (aka Googled) that the array would need to be spread in order for the method to work.

Math.max(…array)

With Math.max(…array), I was able to return the largest value, 4!

With that in mind, I only needed to compare the amount of times 4 appeared. There were several ways of doing this, but I settled on the filter method, which returns a new array for all the elements that match a given condition (in this case, each value that is 4).

arr.filter(num => Math.max(...arr) === num)

This returns an array [4, 4, 4], and so all that’s needed is to return the length of it.

arr.filter(num => Math.max(...arr) === num).length

In a repl, the results worked as expected with my sample array ([1, 2, 2, 4, 4, 4]). However, when I tried to submit the problem to the site, I was hit with a timeout error. It appeared that the solution took too long for arrays that were thousands of elements long.

Not only that, but this solution is creating another array that won’t really be used besides for the purposes of taking its length. Is there a more optimized way of doing things?

For loop solution

Not wanting to get hit by timeout errors again, I returned to my initial idea of using a for loop. I also decided on using a sorted array to grab the max value immediately.

let sort = arr.sort((a,b) => b - a); 
let count = 0;

There were a few things I needed to keep in mind for this sorted array and counter method to work. First, I needed to make sure to keep track of duplicate values. I decided a comparison would take care of this.

for(let i = 0; i < sort.length ; i++){
        if(sort[0] !== sort[i]){
            return count
        } 

        count++
    }

sort[0] represents the max value here since the array has been sorted in decreasing order.

Second, I needed to account for instances where the arrays were filled with the same value.

In the end, the solution looked like this.

    let sort = arr.sort((a,b) => b - a)
    let count = 0;
    for(let i = 0; i < sort.length ; i++){
        if(sort[0] !== sort[i]){
            return count
        } 

        count++
    }
   return count

This solution did pass the tests.

One liner vs for loop

Although the one liner was a lot less code, it ended up being significantly slower than the for loop solution. Using console.time, the execution time was 76.631ms for a 100 element array.

Compared to the for loop, which took 0.319ms, that’s a LOT longer.

Summary

I’m sure there’s solutions out there that account for shorter execution times and less code. Knowing how the time complexity of each method in a one-liner can affect the overall performance of a function is something important to keep in mind.

You can find this problem on hackerrank.

Comments

[Glenn Harris]

Thanks for posting this.

Without getting into filter vs for loop, part of the reason the filter ran so long was because Math.apply is being rerun for every element in the array. It is more performant to run it once and assign the value to a variable and then run the comparison against the variable.

jsben.ch/IOkIn

[hidden_dude]

Filter is just the wrong tool for the job. Use a reduce() instead.

Map: convert one elements of an array to an array of something else
Filter: create a new array with certain items removed
Reduce: compute something with the elements of an array

In Smalltalk these were called: collect, select/reject, inject:into: (I like those names better).

martinfowler.com/articles/collecti...

[Joe Avila]

nice catch

[Selin Serin]

this can be an alternative one line solution.
here

[hidden_dude]

I don't get it.
I tried with:

const arr = [100, 22, 22, 44, 44, 44,44];

It doesn't seem to work.

[Selin Serin]

sorry, i forgot to mention.
You need to write the sort function explicitly. Otherwise sorts as a string and 4 > 1 :)

   arr.sort((a, b) => a - b)

[Jakub T. Jankiewicz]

Clever.

[hidden_dude]

The one liner solution here would be to use reduce.
Or map and reduce.

It's important to use the right tool for the job.

For example:

1. Map the array to the tuple: (num, occ). Ie. number and occurrences, where it would be mapped to 1 initially.
   For example:
   [1,2,3,2,3] => [(1,1),(2,1),(3,1),(2,1),(3,1)]

2. Reduce to find the max and sum occurrences:
   [(1,1),(2,1),(3,1),(2,1),(3,1)] => (3,2)

Then you basically have your solution that is O(N) so it's faster than solutions based on sort.

Reduce is what you need to convert a list of values into a single solution. But sometimes you need to convert the list into something else to be able to reduce it.

The code would be something like:

arr.map( n => [n,1]).reduce( (result, tuple) =>  
     (result[0] > tuple[0]) ? result :
          (result[0] == tuple[0]) ? [result[0], result[1]+1] :
               tuple)

The lambda can probably be written clearer.

[hidden_dude]

If you hate the double loop you can avoid the map like this:

arr.reduce( (result, num) =>  
     (result[0] > num) ? result :
          (result[0] ==num) ? [result[0], result[1]+1] :
               [num,1],  (arr[0],0))

This does it all in one pass.

[hidden_dude]

In some languages map/reduce are lazy so it's super efficient to do this (ie. it only goes through the array once). Not sure about Javascript though.

Still, going through the array twice is still more efficient than sorting. Though it's a pity the array has to be copied (in Java or .Net the array wouldn't need to be copied for example, so in theory it's as efficient as the raw for loop, but more readable).

[Kailana Kahawaii]

Awesome! I love seeing solutions like these.

[mafflerbach]

I prefer in general the "long" version. It's about readability. I may have to read more, but it is more clear what happens, especially when I have to switch between multible languages. The general structure from an if/else or a loop are very similar in all languages, but comes to syntactic sugar it becomes difficult.

[Nicolas Torres]

Indeed! For loop is a core syntax element of JavaScript so, if written decently, will always be faster than iterator methods and while loops etc.
To dive further into performance:

• .sort() alters the original array, no need to reassign it, to save a bit of memory :);
• your snippet computes sort.length on each iteration, better store it into a variable;
• count and i have the same value, so you can remove one of them.

Note that for loop first instruction can actually be any set of declarations. So You could directly optimize the code like that:

arr.sort((a,b) => b - a);
let count = 0; // declared outside so it remains in the scope after for loop
for(const n = arr.length; count < n; count++) {
  if (arr[0] !== arr[count]) {
    return count;
  } 
}
return count;

But anyway, .sort() on large arrays will still iterate over all elements. Put like this, it'll be more elegant and should have more or less the same perfs:

const target = Math.max(...arr); // compute once, expensive
return arr.filter(v => v === target).length; // iterate once, cheap

[Nicolas Torres]

And if you really want the best possible perfs, the best option is to iterate once.

It could go like that:

let count = 0;
for (let i = 0, max = 0, n = arr.length; i<n; i++) {
  if (arr[i] > max) {
    max = arr[i];
    count = 1;
  } else if (arr[i] === max) {
    count++;
  }
}
return count;

[Joe Avila]

Great article Kailana.

[Ridoan]

This is interesting, less code not always means better performance

[Ranieri Althoff]

That is never implied, and the problem of this post is not even related to that. It's an inefficient algorithm vs an efficient one problem.