Find the third biggest integer of an array

Question

How can i make this work with fewer lines? The goal here is to get the third biggest integer of an array.

I would also appreciate if someone polished this code.

---

let array = [442, 93, 3, 5, 30, 10];
const f = (arr) => {
 let secureArr = [...arr];
 let big0 = Math.max.apply(null, secureArr);
 const index0 = secureArr.indexOf(big0);
 secureArr.splice(index0, 1);
 let big1 = Math.max.apply(null, secureArr);
 const index1 = secureArr.indexOf(big1);
 secureArr.splice(index1, 1);
 let big2 = Math.max.apply(null, secureArr);
 const index2 = secureArr.indexOf(big2);
 secureArr.splice(index2, 1);
 console.log(Math.min(big0, big1, big2));
};
f(array);

 let array = [442, 93, 3, 5, 30, 10];
 const f = (arr) => {
 let secureArr = [...arr];
 
 let big0 = Math.max.apply(null, secureArr);
 const index0 = secureArr.indexOf(big0);
 secureArr.splice(index0, 1)
 
 
 let big1 = Math.max.apply(null, secureArr);
 const index1 = secureArr.indexOf(big1);
 secureArr.splice(index1, 1);
 
 let big2 = Math.max.apply(null, secureArr);
 const index2 = secureArr.indexOf(big2);
 secureArr.splice(index2, 1);
 
 console.log(Math.min(big0, big1, big2));
 
 };
 f(array);

Answer 1

1. Generally, you want to separate printing from logic. Have your function return the third biggest instead of printing it, and print the return value. This allows you to include the function in a larger project without needing to make any changes.
2. https://softwareengineering.stackexchange.com/q/364086 and https://stackoverflow.com/q/34361379/2336725 recommend function f(arr) {} instead of const f = (arr) => {}. But f is a terrible name for a function. Let's change it to thirdBiggest.
3. There's no real point to the Math.min at the end. You know that big0 is the biggest, big1 is the biggest after that, and big2 the biggest after that. Lets just return big2.
4. You never change the big# values, so they should be constants. But it would be better to reuse the big# and index# variables. I'm going to rename them to big and bigIndex.
5. But now we see that we're repeating the exact same steps three times. Let's move that into a for loop.
6. We might as well use an array spread instead of .apply
7. secureArr implies some sort of security consideration, which I'm not seeing. If you're just wanting to not modify the original, lets call it a copy. Here's where we are now:

let array = [442, 93, 3, 5, 30, 10];
function thirdBiggest(arr) {
 let arrCopy = [...arr];
 let big, bigIndex;
 for ( let i = 0 ; i < 3 ; i++ ) {
 big = Math.max(...arrCopy);
 bigIndex = arrCopy.indexOf(big);
 arrCopy.splice(bigIndex, 1);
 }
 return big;
}
console.log(thirdBiggest(array));

8. You specifically mentioned fewer lines. This is not usually a good metric. If that's all you want, then you should go with Bens Steves' approach and your function will be two lines long. But it will be measurably slower for large arrays.
9. "third biggest" is a bit arbitrary, and now that we have a loop, we can see that it's not hard to turn that into a parameter. Let's do that, and change thirdBiggest into nthBiggest.
10. The usual approach for this problem is that you go through the array once, and keep track of the highest values you've seen so far. If you see a new highest value, it pushes the bottom one off of the list. That ends up being:

function nthBiggest(arr,n) {
 // start with the front of the array
 let biggestValues = arr.slice(0,n);
 biggestValues.sort( (a,b) => a-b );
 // now look through the rest of the array
 arr.slice(n).forEach( (value) => {
 if ( value > biggestValues[0] ) {
 biggestValues.shift();
 let valueIndex = biggestValues.findIndex( (big) => big>value );
 if ( valueIndex >= 0 ) {
 biggestValues.splice(valueIndex,0,value);
 } else {
 biggestValues.push(value);
 }
 }
 });
 return biggestValues[0];
}
console.log(nthBiggest(array,3));

That's more lines than your original version, but should be the fastest.

• Matthieu M.: The use of an array for biggestValues is problematic from an algorithmic complexity point of view. The issue is that all operations on the array are O(n), and therefore using nthBiggest to find the minimum will have O(n*n) complexity. The most efficient there would be a min-heap, I expect, to get that down to O(n log n). And... that's when you realize that this algorithm has a name: this is the Selection Algorithm, and there's quite a bit of literature about it.
• Peter Cordes: @MatthieuM.: The size of the biggestValues is different from the size of the whole arr. Let's say n (n biggest) and m (arr.length). Then yes, the worst case is O(n*m) in the case where arr has many new max-candidates. (e.g. an overall increasing trend, so the number of updates to the candidate list is also O(m)). But the average case for random data is lower, isn't it? The likelihood of seeing a value higher than any of the highest 5 you've seen before decreases the more you see, I'd guess quickly enough to matter. Unless you use a branchless SIMD sorting network to update it..
• Peter Cordes: Ah, in comments on the sorting answer, you already described the question's approach as O(n*k). Oh, and you said using this to find the minimum, so calling it with n = m. That would basically be user error; this version is clearly optimized for n << m, and if you want the min of a large array you should do that.
• Peter Cordes: It's also insane to only return one value, when in fact you're finding all n largest values: just return the sorted list so finding the 3 largest values takes one call to this function, one pass over the data. That's the whole point of this vs. max / search / replace with a tiny value or remove / repeat, for arrays that fit in cache. (Plain Max and indexof are optimizable with SIMD, and in Python hopefully at least have compiled C implementations even if it's just scalar.

Answer 2

Generally

To get the n biggest integer in an array you want to first sort the array of integers. Finally, you can index the array by array.length - n.

Example: Third Largest Number in Array

const arrNumbers = [442, 93, 3, 5, 30, 10];
// First Step: Sort Array
const sortedArray = arrNumbers.sort((a,b) => a - b);
// Final Step: Get Third to Last Number in Array
const thirdLargest = sortedArray[sortedArray.length - 3];
console.log(thirdLargest);
const assertion = thirdLargest === 30;
console.log(assertion)

• Teepeemm: But sorting is an n log n operation. OP's approach is O(n).
• Matthieu M.: @Teepeemm: For a generic version of selecting the k-th largest, OP's approach is O(n * k); depending how large k is related to log n, sorting may offer better complexity. Also... this approach has the advantage of being very easy to understand, which is a clear advantage.
• qwr: For top k numbers, you can maintain a k-size max-heap. But that is probably not faster in practice for small k.

Answer 3

• Naming could be better
  • I prefer list over array, shorter to type and avoids the temptation to use arr as a variable
  • f is a meaningless name for a function, go with <verb><thing>
• let big0 could be const big0
• you use index0 only once, I would have used secureArr.indexOf(big0) in the splice call
• The code has a block of code that got copy pasted twice, consider applying DRY techniques
• Personally, I would replace this with a one-liner until I see it really is too slow
• If it did get too slow, I would replace this with an old fashioned for loop
• let big1 = Math.max.apply(null, secureArr); -> let big1 = Math.max(...secureArr);
• Calculating and outputting should happen in different locations
• I think using the function keyword would have been more readable

Mandatory rewrite

const input = [442, 93, 3, 5, 30, 10];
 
 function getNthLargest(list, n=3){
 return [...list.sort((a, b)=>b-a)][n-1];
 }
 
 console.log(getNthLargest(input,3));

Answer 4

In general, to find the kth largest number, calling indexOf k times, with each call linear time, will lead to O(n*k) time complexity. (Also splice() may be slow - not sure if this is linear time per call). This is fine for small k.

A one-liner solution is to sort an array and take the kth largest number. This is O(n log n) and I assume the simplest and fastest method in practice, since sorting integers should be optimized.

For k much smaller than n, you can iterate over all values and track the top-k smallest values in a min-heap limited to size k (inserting new value, then popping the smallest value at the top), then at the end you are left with the top-k largest values, with kth largest at the top of the heap, in total O(n log k) time. This generalizes maintaining the max value for the k=1 case. You can also maintain order statistics with an order-statistic tree if you need faster lookup, insertion, and deletion. This is overkill for a simple array.

• Peter Cordes: You'd want a min-heap since you want to remove the smallest out of the k-highest every time you insert a new candidate that's higher than the lowest of the candidate's you've seen thus far. But yes, then you can return that whole list of k'th highest values, instead of just one of them, so the caller only needs to call it once, not once for each output value.
• qwr: @PeterCordes yeah you're right. It's been a while since I implemented this but afterwards, the kth largest value should be at the top of the heap and can be popped and returned.