6

So, I was working on this challenge to return the third largest number in an array. I had got it worked out until I realized that I must account for repeat numbers. I handled this by adding 3 layers of for loops with variables i, j, and k. You'll see what I mean in the code. This is not terribly efficient or scalable.

My question is, how can I optimize this code? What other methods should I be using?

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
Improve this question
4
  • @jtbandes: Have a look at the OP's code. Commented May 18, 2016 at 1:10
  • 2
    Well that's embarrassing. Commented May 18, 2016 at 1:10
  • 1
    You can maintain a tiny array of 3 elements: add another element to the array (if it's different), sort, chop the 4th element. That way the complexity of a solution would be linear to the number of elements in the original array. Commented May 18, 2016 at 1:14
  • You might want to look at implementing Introselect Commented May 18, 2016 at 1:27

6 Answers 6

Reset to default
3

Since you already sorted the array, it seems like you should be fine iterating over the list and keep track of the numbers you have already seen. When you have seen three different numbers, return the current one:

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 to

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

The callback has to return a number that is larger, smaller or equal to 0, it doesn't have to be exactly -1 or 1.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

A one-"line"r using Set to remove duplicates

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

Set now has reasonable browser support

Improve this answer

6 Comments

nice, this is pretty.
Yes. Even tighter [...new Set(arr)].sort((a,b) => a-b)[2]
This is a potential out of bound access, not "pretty".
@zerkms Out of bounds? What am I missing? Oh ... [1,1,1,1] would barf. Great catch!
@zerkms is referring to what happens if arr = [1, 1, 1, 1]. But the question is ill-posed in that case anyway, so throwing an error is the right thing to do.
|
3

The optimal solution is to do this in a single pass O(n) time. You do not need to sort the array - doing so makes your solution at-least (n log n).

To do this in as single pass, you simply need three temporary variables: largest, secondLargest, thirdLargest. Just go through the array and update these values as necessary (i.e. when you replace largest it becomes second largest, etc...). Lastly, when you see duplicates (i.e. currentValue == secondLargest), just ignore them. They don't affect the outcome.

Don't forget to check for edge cases. You cannot provide an answer for [2, 2, 2, 2, 2] or [3, 2].

Improve this answer

1 Comment

Your answer deserves to be accepted, you are the only one to explain that sorting is overkill.
1

Try to think about what data structure you can use here. I suggest a set. Every time you add a nested loop your function gets exponentially slower.

Edited:

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 get an array passed in.

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

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

Improve this answer

5 Comments

a + b should probably be b - a?
Or more clearly, use Map
can you explain what this does , I dont quite get the syntax arr.forEach(function(num) { map[num] = ++map[num] || 1; }); The key's value is either 1 or +1 ?
edited my answer, its a way to make an object where the numbers in the array are keys, and there can only be one key per number its a just a way to get rid of the duplicates.
Why not just map[num] = true?
0

Many of the other answers require looping through the initial array multiple times. The following sorts and deduplicates at the same time. It's a little less terse, but is more performant.

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
Improve this answer

Comments

0

One single iteration O(n) and very fast method of doing this is making your own Set like object. The advantageous point is making no comparisons at all when constructing our "sorted" list of "unique" elements which brings enormous efficiency. The difference is very noticeable when dealt with huge lists like in the 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 Object.keys might not return a sorted array (which i haven't yet seen not) then you can just sort it like it's done in the Set method.

Here i tried it for 1,000,000 item array and returns always with the correct result in around 45msecs. A 10,000,000 item array would take like ~450msec which is 50% less than other O(n) solutions listed under 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);

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.