Most efficient way to find max/min element in array of array

Question

I'd like to know how Can I return the min/max element in array of array Efficiently. I know I can do a loop throught the array but I think there may be a better option.

let tab= [2];
tab[0] = [{name :"book", value : 8}, {name :"cake", value : 2}]
tab[1] ... etc

I want to find the min or max value in this array for example.

I go with Math.max.apply to do that since it's referencing the array while reduce duplicates it. But if you don't care about that you totally should use reduce like it is said below.

@LuisfelipeDejesusMunoz This is very inefficient way to find min/max values. — Yury Tarabanko, Sep 26 '18 at 13:03
Possible duplicate of [Finding the max value of an attribute in an array of objects](https://stackoverflow.com/questions/4020796/finding-the-max-value-of-an-attribute-in-an-array-of-objects) — Calvin Nunes, Sep 26 '18 at 13:03
Is the array sorted? If so, you can grab the first (or last) value to get what you need. Is the array not sorted? You need to either do a linear scan for O(n) or sort it which is unlikely to give you O(n). There is no magical way to know what is the smallest value in an unsorted array without checking everything. — VLAZ, Sep 26 '18 at 13:05
@LuisfelipeDejesusMunoz But it is worse than straight forward loop which is only `O(n)` — Yury Tarabanko, Sep 26 '18 at 13:07
@CalvinNunes there seems to be only one answer on that page that is efficient. The accepted answer, for example, isn't as it goes through the array once, builds another array and then goes through it again for an O(2n) in both time and space complexity. — VLAZ, Sep 26 '18 at 13:09
@vlaz "There is no magical way to know what is the smallest value in an unsorted array without checking everything." there is sort of magical way to do it in `O(sqrt(n))` [if you have a quantum computer](https://arxiv.org/pdf/quant-ph/9607014.pdf) :) — Yury Tarabanko, Sep 26 '18 at 13:10
@YuryTarabanko woah interesting paper. I love the sentence "The probability of success can be improved by running the algorithm c times" :D — VLAZ, Sep 26 '18 at 13:12
@vlaz As usually when it comes to quantum computation. But anyway `c` is independent of `n` :) — Yury Tarabanko, Sep 26 '18 at 13:19

score 0 · Answer 1 · answered Sep 26 '18 at 13:16

0

There are many ways of doing it. The first one is to reduce the array maintaining the max/min value:

let tab= [2];
tab[0] = [{name :"book", value : 8}, {name :"cake", value : 2}]
tab[1] = [{name :"apple", value : 1}, {name :"spaceship", value : 200}]

console.log(
  tab.map(a=>a.reduce((a,b)=>a.value>b.value?a:b,{})).reduce((a,b)=>a.value>b.value?a:b,{})
)

This can be easier if we flatten the array as follow

let tab= [2];
tab[0] = [{name :"book", value : 8}, {name :"cake", value : 2}]
tab[1] = [{name :"apple", value : 1}, {name :"spaceship", value : 200}]

console.log(
  [].concat.apply([], tab).reduce((a,b)=>a.value>b.value?a:b,{})
)

Those above functions get the max value, to get the min simply change a.value>b.value to a.value<b.value. Also, those functions has a time complexity of O(n) so with larger arrays it will work faster.

The other way is to sort and get the first/last value

let tab= [2];
tab[0] = [{name :"book", value : 8}, {name :"cake", value : 2}]
tab[1] = [{name :"apple", value : 1}, {name :"spaceship", value : 200}]

console.log(
  [].concat.apply([], tab).sort((a,b)=>b.value-a.value)[0]
)

However this method is more complex as it sorts the array first (O(n log n)) and then gets the first or last element (O(1)).

answered Sep 26 '18 at 13:16

Luis felipe De jesus Munoz

7,454
2
33
53

`Also, those functions has a time complexity of O(n)` but the second technique makes an entirely new array. Moreover, with a large enough input array of arrays, it would be growing and *resizing* which can add a significant overhead in addition to the space complexity required for using memory for the second array. It's therefore not as performant as just statically walking the array of arrays. The first technique could be re-written as a recursive function, which would handle arbitrary depth of arrays and would even be pretty simple to read. – VLAZ Sep 26 '18 at 13:30
This [jsPerf test](https://jsperf.com/native-array-methods-vs-for-loop/1) shows how native array methods are slower than basic for loops. – Adam Sep 26 '18 at 13:50
Interesting. Looks like it depends on external factors then. – Adam Sep 26 '18 at 13:56
Indeed I have larger arrays, that's why I was digging the question. I will try both of them in order to compare their time execution. – Kalkal Sep 26 '18 at 13:59
Finally, I rather use Math.max.apply to get it since reduce "duplicates" the array while apply references it – Kalkal Sep 26 '18 at 14:48

Most efficient way to find max/min element in array of array

1 Answers1