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();

Answer 1

Assuming a fairly normal distribution, this should be fairly optimal:

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

max_three = (function (numbers) {
    var i, one, two, three;
    one = Number.NEGATIVE_INFINITY;
    two = Number.NEGATIVE_INFINITY;
    three = Number.NEGATIVE_INFINITY;
    
    for (i = 0; i < numbers.length; i += 1) {
        num = numbers[i];
        if (num > three) {
            if (num >= two) {
                three = two;
                if (num >= one) {
                    two = one;
                    one = num;
                }
                else {
                    two = num;
                }
            }
            else {
                three = num;
            }
        }
    }
    
    return [one, two, three]

}(numbers))

document.write(max_three)​​​​​​​

98, 93, 91

Answer 2

First you can sort your array, and then the last three items are the answers. sort() and at() methods made it so easy:

scoreByPattern.sort(function(a, b) {return a-b});
console.log(scoreByPattern + "/******/" + scoreByPattern.at(-1) + 
    "/" + scoreByPattern.at(-2) + "/" + scoreByPattern.at(-3));

Answer 3

function findMinAndMax(arr, largestBy=3) {
  arr = arr.sort((a,b) => a-b);

  let arr1 = arr.splice(0,largestBy);

  let highesMin = Math.max(...arr1); 
  console.log('highesMin', highesMin);

  let arr2 = arr.splice(arr.length - largestBy , largestBy);
  let lowestMax = Math.min(...arr2); 

  console.log('lowestMax', lowestMax);

}

let arr = [2,23,1,5,6,45,23,67];

findMinAndMax(arr, 2);

// OP highesMin 2 lowestMax 45

Answer 4

I hope this is the simplest method for finding the three largest numbers in a given array and the three indexes of the three largest numbers.

<script>
      const orginalNumbers = [93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60];
      const orginalCopyNumbers = [];
      const orginalNumbersIndex = [];
      const threeLargestNumber = [];
      orginalCopyNumbers.push(...orginalNumbers);

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

      for(var i=0;i<orginalCopyNumbers.length;i++){
        var index = orginalCopyNumbers.indexOf(orginalNumbers[i]);
        orginalNumbersIndex.push(index);
        threeLargestNumber.push(orginalNumbers[i]);
      }
      var threeLargestNumberIndex = orginalNumbersIndex.slice(0, 3);
      threeLargestNumberArray = threeLargestNumber.slice(0, 3);

      console.log(threeLargestNumberIndex);
      console.log(threeLargestNumberArray);
 </script>

Answer 5

Here is a solution without sorting:

let getLargest = (a,n)=>{
    let max,p,b=[],n1;
    for(let i=0;i<n;i++){
        max=a[0]
        p=false
        n1=0
        for(let j in a){
            if(max<a[j]){
                max=a[j]
                p=true
                n1=j
            }
        }
        if(!!p){
            b.push(max)
            a.splice(n1,1);
        }
    }
    console.log(a)
    return b;
}

console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 3))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 4))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 1))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 2))

for n loops, we are looking for the max and removing it from the original array and pushing it to new array. You can get n large elements.

Answer 6

Edit: Everything below is still valid. However, it was clarified to me in a comment that the original question did not ask for indexes, and many of the answers were responding to the preexisting question. Apologies for any curtness in my original post.

Even looking at the original question however, I still disagree with recommending sorting in general for this type of question.

---

I can't believe how many of these answers are worse than the OP's provided solution. Most are more concise, but either:

• Don't answer the question. Often only providing the top 3 values, when the question also asks for the indexes of the top 3 values.
• Suggest "sorting" but without even mentioning performance, side-effects or Big-O notation.

This may be a little too long for SO, but I feel like this is pertinent information.

---

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

I take (3) to mean "I want the method to be more concise / readable", (2) as "indices to be available in the output directly", and (1) to mean "I want the code to be as efficient as possible".

Starting from (3) as it'd be most useful to people: Your original algorithm is quite efficient, but you're basically duplicating code in each of the 3 loops; the only difference in each loop really is that the index changes. If you just wanted to cut down on the number of characters, you could re-write your algorithm (with a couple minor caveats¹) as:

function findLargest3(arry) {
  const max = {
    indices: new Array(0, 0, 0),
    points : new Array(0, 0, 0)
  }
  
  // Inner private function to remove duplicate code
  // Modifies "max" as a side-effect
  function setLargest (idx) {
    const lastMax = max.points[idx - 1] || Number.MAX_VALUE;
    for (let i = 0; i < arry.length; i++) {
      if (arry[i] > max.points[idx] && arry[i] < lastMax) {
        max.points[idx] = arry[i];
        max.indices[idx] = i;
      }
    }
  }
  
  // Get's the 0'th, 1st, and 2nd largest items
  for (let i = 0; i < 3; i++) {
    setLargest(i);
  }
  
  return max;
}

let scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);
let max = findLargest3(scoreByPattern);
console.log(scoreByPattern + "/******/" + max.points.join("/"));

Beyond the addition of the function, the only thing I really had to add was: const lastMax = max.points[idx - 1] || Number.MAX_VALUE;. This was just for the case where idx == 0. As there is no max.points[-1]. We want that second check to always return true, so if max.points[idx - 1] doesn't exist, set it to the highest possible value via ||.

This actually ends up being about 4 times slower than your implementation. That slowness is a result of not directly modifying global state (which is faster but harder to maintain) & including that inner function rather than the code duplication. Replacing the inner function with your original duplicated code & leaving every other change the same ends up being 40% faster to execute, because it avoids the creation & calling of the function entirely; but again is easier to read. It also makes extending findLargest3 to become findLargest5 or findLargestN much simpler.

Additionally, it should be the same Big-O as your original solution (see my answer to 1), unlike the solutions involving sort; which means it will scale as well as your original solution, while being easier to read & maintain. If you really need the performance, there's very little wrong with your original solution, and I'd even argue your original solution's better than some of the posted solutions. (For example, from rough testing, increasing the size of the array to ~100 elements makes my solution run about ~3x slower, but makes a solution using sort run more than 6x slower).

---

¹Note: There is one major issue with your algorithm, and that's that i is "globally scoped". If you wrote the following, it would run for i==0 and then loop forever with i==scoreByPattern.length & would never finish:

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

That's because your for (i = 0 ... statements don't reference a "local" version of i & will fall back to one that's been defined in a previous scope (or global if it doesn't find one). Your loops always leave i set to scoreByPattern.length when they finish, which would change the value in this outer loop. Certain languages & language constructs (foreach in C# for example) actually won't compile if you've attempted to modify an iterator during a loop. The fix is actually really simple, & it's just to say var i or let i in your loop declaration & then i will only refer to a variable local to the function.

There's also the minor problem of your original algorithm ignoring duplicates in the array. If I add another 93 to the end of your original array, it still returns the top values as [98, 93, 91]. I didn't change this in my solution, as it may be intentional (e.g. the top three "values" are 98, 93, and 91, but 93 just happens to occur twice). To fix, rather than checking that arry[i] < max.points[... you would just check that i isn't already in max.indices. Depending on the number of duplicates, this could slow the algorithm down (without a rewrite) but assuming duplicates << array.length then it wouldn't be noticeably slower.

And while not being a "problem" per-se, it's generally not ideal to have "global state" (i.e. scoreByPattern, maxPoints, maxIndex) & then have them be mutated by a function. It can be computationally faster, but harder to maintain. That's why I moved the declaration of maxPoints / maxIndex into the function body & made it request scoreByPattern as a parameter. There are plenty of scenarios where that'd be fine (e.g. Object member variables & mutator methods). But here, findLargest3 really seems like a helper function / functional in nature, & thus ideally shouldn't have side-effects (i.e. modify external state / the parameters that are passed to it).

---

Briefly mentioning (2): If the indexes themselves matter, sorting the array doesn't really make sense except in some very particular circumstances (see my answer to point 1). Sorting is an "in-place" operation using Javascript's sort method on the array directly. This means it will modify the original array in most of these answers; so the original indexes are actually lost & also has other consequences for the rest of the program. In order to use sort to get the top N values, you'd have to copy the array first, sort the copy, take the top 3 values, then iterate through the original array ~3 times trying to match using indexOf or similar (and dealing with duplicates).

This is obviously a waste of resources, as some of these answers are as much as 30 times slower than the original. You could try and generate a list of "indexes" rather than values, sort them based on the original array, & that'd be slightly faster. But in this specific case where we only want "the top 3" (again, see my answer to point 1) unless I'm crazy, sorting will almost always be slower.

---

Finally, looking at (1) it's useful to apply a concept called "Big-O notation" when analysing algorithms. I'd suggest googling it & having a read, but broad-strokes: we want to see how efficient an algorithm is, as the length of the input increases. E.g. In your application, we've got the array scoreByPattern which we'll say has a length of N, as well as an explicit "3 indexes / values" imposed by your question, but it's useful to be able to say "return the top M indexes / values". If scoreByPattern or top M are very short, then the complexity of the algorithm won't really matter, but if they've got 100's to 100's of thousands of elements, then their computational complexity becomes really significant.

Also, it's important to say that with an array in JS, if you know the index, a "lookup" is actually a nearly instantaneous operation ~Big O(1). Also, in Big-O, we tend to only look at the "dominant" term of an analysis & ignore any constant-time factors. E.g. If a solution is 10x O(1) + 2x O(N) (10 constant time operations + 2 operations for each item in a list of length N) we say the Big-O of the solution is O(N). This is because, for a reasonably long list, if we doubled the value of N, the time taken will roughly double. If it was bounded by an O(N²) operation & the list length was doubled, it would take 2² times longer (i.e. 4 times slower).

So your original solution is:

• Some constant time steps
• Iterate through the list once, do two boolean checks & two assignments
• Do this again
• Do this a third time

Meaning it'd be something like kO(1) + 3*cO(N) where k & c are some constants, leaving it as: O(N) in general. If we wanted the "Top M indexes" you'd end up with: MO(N) which ends up being O(NM) (i.e. Big-O of N * M). Why is this important?

sort is Big-O of O(N Log2(N)) what this means is that for say, a list of ~64 items, sort will take roughly 64 * Log2(64) == 64 * 6 == ~384ish operations. So comparing your solution to ones involving sort, unless M > Log2(N), not sorting is preferable.

To put that into perspective: if your list has 100 items, you'd need to be trying to get more than 6 "largest" items for sorting to be more efficient. If it was 100,000 items, you'd need to be trying to get more than 16 "largest" items. In this use-case, especially since you've explicitly said "3", it almost always makes more sense not to sort. Particularly, because you're trying to get indices; if you only wanted values, then the sorting solutions may be preferable just because they're simple.

You could probably tune your algorithm a bit more to speed it up further, but from rough testing: I think your solution is already the fastest solution here. If you want to make it easier to maintain / read / extend, that's definitely possible; but that really shouldn't come at the expense of actually increasing "time complexity" (i.e. making the solution worse than O(N)) unless it vastly simplifies the implementation.

Answer 7

I created a function that return N indexes of the N largest elements (in the case of equal values, it return the first indexes found). In code, N is qtyMax. Function has cost O(n), in the worst case n * qtyMax.

function maxIdxs(arr, qtyMax) {
    var maxIndex = new Array();
    for(var i=0; i<arr.length; i++) {
        var m=0;
        while(m<qtyMax && arr[i]<=arr[maxIndex[m]])
            m++;
        if(m<qtyMax)
            maxIndex.splice(m, 0, i);
    }
    return maxIndex.slice(0, qtyMax);
}

console.log(maxIdxs( [1,23,46,35,20] , 0 )); // []
console.log(maxIdxs( []              , 3 )); // []
console.log(maxIdxs( [1,23]          , 3 )); // [1,0]
console.log(maxIdxs( [1,23,46,35,20] , 3 )); // [2,3,1]
console.log(maxIdxs( [1,40,40,40,40] , 3 )); // [1,2,3]

To obtain the corresponding function minIdxs (find N indexes of the smallest) you just need to replace <= with >= in the condition of the while.

Answer 8

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

Answer 9

The following function return a array whose element is a fixed two-element array with 1st element as the index and second as its value.

function findTopValues(dataArray, n) {
  var resultArray = [];

  var dataArrayCopy = dataArray.slice();

  var topNArray = dataArrayCopy
    .sort(function (begin, end) {
      return end - begin;
    })
    .slice(0, n);
  for (let ele of topNArray) {
    resultArray.push([dataArray.indexOf(ele), ele]);
  }
  return resultArray;
}

var dataArray = [12,5,20,4,50,23,98,8];

console.log(findTopValues(dataArray,3))

Answer 10

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));
}

Answer 11

function get3TopItems(arr) {
  return arr.sort((a, b) => b - a).slice(0, 3);
}

Answer 12

Here is an optimized solution for your problem without using sort or other complex array method :

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 findTop3(n) {
	for (var i = 0; i < n.length; i ++) {
		if (i === 0) {
			maxPoints.push(n[i]);
			maxIndex.push(i);
		} else if (i === 1) {
			if (n[i] > maxPoints[0]) {
				maxPoints.push(maxPoints[0]);				
				maxPoints[0] = n[i];
				maxIndex.push(maxIndex[0]);
				maxIndex[0] = i;
			} else {
				maxPoints.push(n[i]);
				maxIndex.push(i);
			}
		} else if (i === 2) {
			if (n[i] > maxPoints[0]) {
				maxPoints.push(maxPoints[0]);
				maxPoints[1] = maxPoints[0];
				maxPoints[0] = n[i];
				maxIndex.push(maxIndex[0]);
				maxIndex[1] = maxIndex[0];
				maxIndex[0] = i;
				
			} else {
				if (n[i] > maxPoints[1]) {
					maxPoints.push(maxPoints[1]);
					maxPoints[1] = n[i];
					maxIndex.push(maxIndex[1]);
					maxIndex[1] = i;
				} else {
					maxPoints.push(n[i]);
					maxIndex.push(i);
				}
			}
		} else {
			if (n[i] > maxPoints[0]) {
				maxPoints[2] = maxPoints[1];
				maxPoints[1] = maxPoints[0];
				maxPoints[0] = n[i];
				maxIndex[2] = maxIndex[1];
				maxIndex[1] = maxIndex[0];
				maxIndex[0] = i;
			} else {
				if (n[i] > maxPoints[1]) {
					maxPoints[2] = maxPoints[1];
					maxPoints[1] = n[i];
					maxIndex[2] = maxIndex[1];
					maxIndex[1] = i;
				} else if(n[i] > maxPoints[2]) {
					maxPoints[2] = n[i];
					maxIndex[2] = i;
				}
			}
		}
	}
}
findTop3(scoreByPattern);
console.log('Top Elements: ', maxPoints);
console.log('With Index: ', maxIndex);

Answer 13

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)

Answer 14

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

Answer 15

Why don't you just sort it and take the first (or last if sorted in ascending order) three elements.

var maxPoints = new Array();
var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);
scoreByPattern.sort();
maxPoints[0] = scoreByPattern[scoreByPattern.length - 1];
maxPoints[1] = scoreByPattern[scoreByPattern.length - 2];
maxPoints[2] = scoreByPattern[scoreByPattern.length - 3];

Edit
If you need the indeces of the largest arrays you can make a copy which you sort and then find the indices in the original array:

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

// Make a copy of the original array.
var maxPoints = scoreByPattern.slice();

// Sort in descending order.
maxPoints.sort(function(a, b) {
    if (a < b) { return 1; }
    else if (a == b) { return 0; }
    else { return -1; }

});

// Find the indices of the three largest elements in the original array.
var maxPointsIndices = new Array();
maxPointsIndices[0] = scoreByPattern.indexOf(maxPoints[0]);
maxPointsIndices[1] = scoreByPattern.indexOf(maxPoints[1]);
maxPointsIndices[2] = scoreByPattern.indexOf(maxPoints[2]);

Another approach to find the indices without sorting is this:

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

for (var i = 0; i < scoreByPattern.length; i++) {
  if (maxIndices[0] < scoreByPattern[i]) {
    maxIndices[2] = maxIndices[1];
    maxIndices[1] = maxIndices[0];
    maxIndices[0] = scoreByPattern[i];
  }
  else if (maxIndices[1] < scoreByPattern[i]) {
    maxIndices[2] = maxIndices[1];
    maxIndices[1] = scoreByPattern[i];
  }
  else if (maxIndices[2] < scoreByPattern[i]) maxIndices[2] = scoreByPattern[i];
}

Answer 16

http://jsfiddle.net/GGkSt/

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

function cloneArray(array) {
    return array.map(function(i){ return i; });
}    
function max3(array) {
    return cloneArray(array).sort(function(a,b) { return b-a; }).slice(0,3);
}
function min3(array) {
     return cloneArray(array).sort(function(a,b) { return a-b; }).slice(0,3);
}

var array=scoreByPattern;
alert("Max:"+ max3(array)[0] +' '+max3(array)[1] +' '+max3(array)[2]);
alert("Min:"+ min3(array)[0] +' '+min3(array)[1] +' '+min3(array)[2]);

Answer 17

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;
});