Optimized javascript code to find 3 largest element and its indexes in array?

Question

I need a more optimized version of this javascript code to find the 3 largest values in an array. I need to get the indexes of the largest numbers. Are there any other easier methods to solve the problem?

var maxIndex = new Array();
var maxPoints = new Array();
var scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);

function findLargest3() {
  maxPoints[0] = 0;
  maxPoints[1] = 0;
  maxPoints[2] = 0; 
  
  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[0]) {
      maxPoints[0] = scoreByPattern[i];
      maxIndex[0] = i;
    }
  }

  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[1] && scoreByPattern[i] < maxPoints[0]) {
      maxPoints[1] = scoreByPattern[i];
      maxIndex[1] = i;
    }
  }

  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[2] && scoreByPattern[i] < maxPoints[1]) {
      maxPoints[2] = scoreByPattern[i];
      maxIndex[2] = i;
    }
  }

  console.log(scoreByPattern + "/******/" + maxPoints[0] + "/" + maxPoints[1] + "/" + maxPoints[2]);
  //alert(maxIndex);
}

findLargest3();

Solution 1

You can sort the array descending. Then the indexes of the highest 3 values will be the first three items in the array. You can access them individually or use slice() to get them at once. The example below shows both methods.

var maxPoints = new Array();
var scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);

findLargest3();

function findLargest3() {
  scoreByPattern.sort((a, b) => a < b ? 1 : a > b ? -1 : 0);
  
  console.log(scoreByPattern + "/******/" + scoreByPattern[0] + "/" + scoreByPattern[1] + "/" + scoreByPattern[2]);  
  console.log(scoreByPattern.slice(0, 3));
}

Solution 2

Modified version

I have modified my answer to make it more generic. It searches for the indices of the n largest numbers of elements in the array:

var scoreByPattern = [93,255,17,56,91,98,33,9,38,55,78,29,81,60];

function findIndicesOfMax(inp, count) {
    var outp = [];
    for (var i = 0; i < inp.length; i++) {
        outp.push(i); // add index to output array
        if (outp.length > count) {
            outp.sort(function(a, b) { return inp[b] - inp[a]; }); // descending sort the output array
            outp.pop(); // remove the last index (index of smallest element in output array)
        }
    }
    return outp;
}

// show original array
console.log(scoreByPattern);

// get indices of 3 greatest elements
var indices = findIndicesOfMax(scoreByPattern, 3);
console.log(indices);

// show 3 greatest scores
for (var i = 0; i < indices.length; i++)
    console.log(scoreByPattern[indices[i]]);

Here is a jsFiddle

Solution 3

Without sorting the huge array: Runs in O(n) which is superior to anything that involves sorting the original array. Returns an array of the largest values and their indices in the initial array. With some smarter code you can eliminate the sorting of the small array which results in a better worst-case performance.

var ar = [93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60];
console.log(`input is: ${ar}`);

function getMax(ar){
    if (ar.length <= 3) return ar;
    let max = [{value:ar[0],index:0},
               {value:ar[1],index:1},
               {value:ar[2],index:2}];
    max.sort((a,b)=>a.value-b.value);
        
    for (let i = 3;i<ar.length;i++){
        if (ar[i] > max[0].value){
           max[0] = {value:ar[i],index:i};
           max.sort((a,b)=>a.value-b.value);
        }
    }
    return max;
}

result = getMax(ar);

console.log('the three largest values are:');
console.log(result);

Solution 4

The default javascript sort callback won't work well because it sorts in a lexicographical order. 10 would become before 5(because of the 1)

No credit to me but:

my_array.sort(function(a,b) {
    return a-b;
});

Solution 5

The best way is to use a combination of sort and slice:

This simple one liner will solve your problem.

[1, -5, 2, 8, 17, 0, -2].sort(function(a, b){return b - a}).slice(0, 3)

So if you have an array and want to find N biggest values:

arr.sort(function(a, b){return b - a}).slice(0, n)

And for N smallest values:

arr.sort(function(a, b){return a - b}).slice(0, n)

View more solutions