Max / min of large array in JS

Question

I need to calculate min/max of large array. I know about Math.max.apply(), but on large arrays it fails with Stack overflow exception. Any simple solutions?

True, but there are better ways to do it on the server side than Javascript, so I made an assumption. Why Javascript? — George Cummins, Jun 05 '13 at 18:28
In fact it is a part of CLI script. My preference would be Python, but 1) my team decided to use JS 2) we use Azure and Windows, and node is easiest to setup to have cross-platform script tools. — Alexey Timanovsky, Jun 05 '13 at 19:15

score 7 · Accepted Answer · edited Apr 22 '21 at 21:05

7

Sort the array by using sort() method it sorts array by using quicksort algorithm

Since array is sorted in ascending order then the last element is the max

var arr = [1,4,6,4, ...];
arr.sort((a, b) => a - b);
var max = arr[arr.length - 1];

edited Apr 22 '21 at 21:05

Zarel

2,201
1
15
20

answered Jun 05 '13 at 18:25

Nick

4,146
1
18
29

2

You answer made me feel really stupid :(. In fact I already have sorted array. That's why you want code reviews... – Alexey Timanovsky Jun 05 '13 at 19:12
Just keep it DRY = Don't Repeat Yourself :) – Nick Jun 05 '13 at 19:23
3

It's only worth sorting the array if you're going to be doing some binary searches [O(log n)] on the array anyways. If you want to get the max and min you might as well loop through every element since O(n) is faster than O(n log n). For lots of large arrays this might matter... – David Sherret Jun 05 '13 at 19:23
1

Sure. I have sorted array in order to calculate percentiles. Having min/max is a nice side effect :) – Alexey Timanovsky Jun 05 '13 at 19:35

score 3 · Answer 2 · edited May 23 '17 at 12:26

3

Array.prototype.min = function() {
    var r = this[0];
    this.forEach(function(v,i,a){if (v<r) r=v;});
    return r;
};

From JavaScript: min & max Array values? where other solutions from this problem are discussed

FYI: I just googled "max min large array" and found this as the first result...

edited May 23 '17 at 12:26

Community

1
1

answered Jun 05 '13 at 18:22

Antoine

2,775
15
23

I saw that thread, but didn't go through all of it, thanks :) – Alexey Timanovsky Jun 05 '13 at 18:26
For reference, the exact answer there that addresses large arrays is this one: http://stackoverflow.com/a/8986992/710446 – apsillers Jun 05 '13 at 18:26

David Sherret · Answer 3 · 2013-06-05T18:27:47.607

Why not just loop through the entire array?

var max = Number.MIN_VALUE, min = Number.MAX_VALUE;
for (var i = 0, len=list.length; i < len; i++) {
   if (list[i] > max) max = list[i];
   if (list[i] < min) min = list[i];
}

Edit:

For max:

if (typeof Array.prototype.GetMax === "undefined") {
    Array.prototype.GetMax = function() {
        var max = Number.MAX_VALUE;
        for (var i = 0, len=this.length; i < len; i++) {
           if (this[i] > max) max = this[i];
        }
        return max;
    }
}

For min:

if (typeof Array.prototype.GetMin === "undefined") {
    Array.prototype.GetMin = function() {
        var min = Number.MIN_VALUE;
        for (var i = 0, len=this.length; i < len; i++) {
           if (this[i] < min) min = this[i];
        }
        return min;
    }
}

For both:

if (typeof Array.prototype.GetMaxMin === "undefined") {
    Array.prototype.GetMaxMin = function() {
        var max = Number.MIN_VALUE, min = Number.MAX_VALUE;
        for (var i = 0, len=this.length; i < len; i++) {
            if (this[i] > max) max = this[i];
            if (this[i] < min) min = this[i];
        }
        return { Max: max, Min: min};
    }
}

Just init `min`/`max` with `Number.MAX_VALUE`/`Number.MIN_VALUE`. Then you can drop the first if condition. — Sirko, Jun 05 '13 at 18:22
And this can be added to array.prototype to make it easier to use — Yuriy Galanter, Jun 05 '13 at 18:22
BTW, I'd initialize it using first element to support non-numeric values too — RiaD, Jun 05 '13 at 18:30

score 0 · Answer 4 · answered Jun 05 '13 at 18:21

0

Should I assume you have thought of this:

var maxSoFar = -9999999;
for (var i = 0; i < array.length ; ++i) {
    if (array[i] > maxSoFar) {
        maxSoFar = array[i];
    }
    ... similar for minSoFar ...
}

answered Jun 05 '13 at 18:21

Lee Meador

12,521
1
31
39

Yes, I thought... I was looking for something more functional style :) – Alexey Timanovsky Jun 05 '13 at 18:22

score 0 · Answer 5 · answered Jun 05 '13 at 18:28

try this

var arr = [];
for(var i=1000000;i>0;i--)
{
    arr.push(i);
}
//we create a copy of the original array through arr.concat() since we do not want to change the original sorting order of the array
//we pass a function in the sort method as by default it sorts alphabetically instead of numerically. So 99 will be smaller than 100.
var arrMaxMin = arr.concat().sort(function(a,b){return a-b});

arrMaxMin[0]; //min
arrMaxMin[arrMaxMin.length - 1]; //max

score 0 · Answer 6 · answered Jun 05 '13 at 18:33

0

Hey why dont you slice your array into smaller arrays then on that arrays you can easily use Math.max.apply(Math,individual arrays).But remember to reinitialize all subarrays back to null so as to get the memory back once desired max value is obtained

answered Jun 05 '13 at 18:33

chetan mehta

359
1
3
13

Max / min of large array in JS

6 Answers6