Optimization - getting the third largest number in the array

Question

So, I worked on this task to return the third largest number in the array. Everything worked out until I realized that I had to take into account the repeated numbers. I processed this by adding 3 layers for loops with variables i , j and k . You will see what I mean in the code. It is not very efficient or scalable.

My question is how can I optimize this code? What other methods should I use?

 function thirdGreatest (arr) { arr.sort(function(a, b) { if (a < b) { return 1; } else if (a > b) { return -1; } else { return 0; } }); for ( var i = 0; i < arr.length; i++) { for (var j = 1; j < arr.length; j++) { for (var k = 2; k < arr.length; k++) { if (arr[i] > arr[j]) { if (arr[j] > arr[k]) { return arr[k]; } } } } } } console.log(thirdGreatest([5, 3, 23, 7,3,2,5,10,24,2,31, 31, 31])); // 23 console.log(thirdGreatest([5, 3, 23, 7,3,2,5,10,24,2,31])) // 23 console.log(thirdGreatest([5, 3, 7, 4])); // 4 console.log(thirdGreatest([2, 3, 7, 4])); // 3 

Answer 1

Since you've already sorted the array, it seems like you should be iterating through the list and keep track of the numbers you've already seen. When you see three different numbers, return the current:

 var seen = [arr[0]]; for (var i = 1; i < arr.length; i++) { if (arr[i] !== seen[0]) { if (seen.length === 2) { return arr[i]; } seen.unshift(arr[i]); } } 

 function thirdGreatest (arr) { arr.sort(function(a, b) { return b - a; }); var seen = [arr[0]]; for (var i = 1; i < arr.length; i++) { if (arr[i] !== seen[0]) { if (seen.length === 2) { return arr[i]; } seen.unshift(arr[i]); } } } console.log(thirdGreatest([5, 3, 23, 7,3,2,5,10,24,2,31, 31, 31])); // 23 console.log(thirdGreatest([5, 3, 23, 7,3,2,5,10,24,2,31])) // 23 console.log(thirdGreatest([5, 3, 7, 4])); // 4 console.log(thirdGreatest([2, 3, 7, 4])); // 3 

---

Note. You can simplify the sort callback on

 arr.sort(function(a, b) { return b - a; }); // With arrow functions: // arr.sort((a, b) => b - a); 

The callback must return a number greater than, less than, or equal to 0 , it must not be exactly -1 or 1 .

Answer 2

One line "r" with Set to remove duplicates

 Array.from(new Set(arr)).sort(function(a, b) { return b - a; })[2]; 

Set now reasonable browser support

Answer 3

The optimal solution is to do this in one time O (n). You do not need to sort the array - this makes your decision at least (n log n).

To do this in one pass, you just need three time variables: the largest, the second largest, the third largest. Just go through the array and update these values ​​as needed (i.e. when you replace the largest value, it will become the second largest, etc.). Finally, when you see duplicates (i.e. CurrentValue == secondLargest), just ignore them. They do not affect the result.

Remember to check for edge cases. You cannot provide an answer for [2, 2, 2, 2, 2] or [3, 2].

Answer 4

Try to think about which data structure you can use here. I suggest a kit. Every time you add a nested loop, your function is exponentially slower.

Edited by:

 function thirdGreatest(arr) { var s = Array.from(new Set(arr)).sort(function(a, b) { return a - b; }) return s[2] || s[1] || s[0] || null; } 

Working example

We need to be able to handle:

 [1,2,1,2] // 2 [1,1,1,1] // 1 [] // null 

This assumes that you will receive the array that was passed.

• If you do not have the third largest number, you get the second.
• If you do not have the second largest, you get the first largest.
• If you do not have numbers, you get null

If you want the 3rd largest or nothing, return s[2] || null s[2] || null

Answer 5

Many of the other answers require multiple accesses to the initial array. The following types and deduplications at the same time. It is a little less accurate, but more impressive.

 const inputArray = [5,3,23,24,5,7,3,2,5,10,24,2,31,31,31]; const getThirdGreatest = inputArray => { const sorted = [inputArray[0]]; // Add the first value from the input to sorted, for our for loop can be normalized. let migrated = false; let j; for(let i = 1; i<inputArray.length; i++) { // Start at 1 to skip the first value in the input array for(j=0; j<sorted.length; j++) { if(sorted[j] < inputArray[i]) { // If the input value is greater than that in the sorted array, add that value to the start of the sorted array sorted.splice(j,0,inputArray[i]); migrated = true; break; } else if(sorted[j] === inputArray[i]) { // If the input value is a duplicate, ignore it migrated = true; break; } } if(migrated === false) { // If the input value wasn't addressed in the loop, add it to the end of the sorted array. sorted[sorted.length] = inputArray[i]; } else { migrated = false; } } // Return the third greatest return sorted[2];; }; const start = performance.now(); getThirdGreatest(inputArray); // 23 const end = performance.now(); console.log('speed: ', end - start); // 0.1 - 0.2ms 

Answer 6

One single iteration of O (n) and a very quick way to do this is to make your own object of type Set. The advantage is the lack of comparisons when building our "sorted" list of "unique" elements, which brings tremendous efficiency. The difference is very noticeable when it comes to huge lists, such as lengths exceeding 1,000,000.

 var arr = [5, 3, 23, 7,3,2,5,10,24,2,31, 31, 31], sorted = Object.keys(arr.reduce((p,c)=> (p[c] = c, p),Object.create(null))), third = sorted[sorted.length-3]; document.write(third); 

If you think that Object.keys might not return a sorted array (which I haven't seen yet), you can just sort it in the same way as in the Set method.

Here I tried it for a 1,000,000 array of elements and always returned with the correct result in about 45 ms. An argument of size 10,000,000 will take approximately 450 ms, which is 50% less than the other O (n) solutions listed in this question.

 var arr = [], sorted = [], t0 = 0, t1 = 0, third = 0; for (var i = 0; i<1000000; i++) arr[i] = Math.floor(Math.random()*100); t0 = performance.now(); sorted = Object.keys(arr.reduce((p,c)=> (p[c] = c, p),Object.create(null))); third = sorted[sorted.length-3]; t1 = performance.now(); document.write(arr.length + " size array done in: " + (t1-t0) + "msecs and the third biggest item is " + third);