DEV Community

loading...

Are one-liners always the best solutions?

Kailana Kahawaii
Fullstack Javascript | React | Ruby | Rails
・3 min read

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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;
Enter fullscreen mode Exit fullscreen mode

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++
    }
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (17)

Collapse
harrisgca profile image
Glenn Harris • Edited

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

Collapse
aminmansuri profile image
hidden_dude • Edited

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...

Collapse
javila35 profile image
Joe Avila

nice catch

Collapse
slnsrn profile image
Selin Serin • Edited

this can be an alternative one line solution.
here

Alt text of image

Collapse
aminmansuri profile image
hidden_dude

I don't get it.
I tried with:

const arr = [100, 22, 22, 44, 44, 44,44];
Enter fullscreen mode Exit fullscreen mode

It doesn't seem to work.

Collapse
slnsrn profile image
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)
Enter fullscreen mode Exit fullscreen mode
Collapse
jcubic profile image
Jakub T. Jankiewicz

Clever.

Collapse
aminmansuri profile image
hidden_dude • Edited

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)
Enter fullscreen mode Exit fullscreen mode

The lambda can probably be written clearer.

Collapse
aminmansuri profile image
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))
Enter fullscreen mode Exit fullscreen mode

This does it all in one pass.

Collapse
aminmansuri profile image
hidden_dude • Edited

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).

Collapse
kahawaiikailana profile image
Kailana Kahawaii Author

Awesome! I love seeing solutions like these.

Collapse
mafflerbach profile image
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.

Collapse
noclat profile image
Nicolas Torres • Edited

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;
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
Collapse
noclat profile image
Nicolas Torres • Edited

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;
Enter fullscreen mode Exit fullscreen mode
Collapse
javila35 profile image
Joe Avila

Great article Kailana.

Collapse
ridoansaleh profile image
Ridoan

This is interesting, less code not always means better performance

Collapse
rsa profile image
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.