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.
- 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?
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 caveats1) 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).
1Note: 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(N2) operation & the list length was doubled, it would take 22 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.
