Find keys of the 3 largest values in a Javascript Object with O(n) complexity?

Question

Say you have an object such as:

let objToCheck = {
  a: 2, 
  b: 5,
  c: 9,
  d: 33
};

How would you go about returning the keys of the three largest values in ascending order, which in this case would be: [ 'c', 'h', 'd' ], in linear time? Evidently you need to loop through the entire object once to compare all values, but I'm having troubling coming up with a solution that doesn't involve nested loops which I believe is O(n²). Here is what my solution currently looks like so far:

function findBig3 (obj){
  const res = [];
  const largest = Object.values(obj).sort((a,b) => { return b-a }).slice(0,3);

  for (let key in obj){
    largest.forEach((val) => {
      if (obj[key] === val) res.push(key);
        }
    });
  }
  return res;
}

I would imagine you need to declare three variables, such as big1, big2, big3, and as you loop through the object do some type of comparison check and reassign as appropriate, but I'm struggling with the implementation.

Answer 1

This algorithm runs in O(n).

function getThreeLargestKeys(obj){
    var k1, k2, k3;
    var v1, v2, v3;
    v1 = v2 = v3 = -Infinity;

    // O(1)
    var insertKey = function(key){
        var value = obj[key];  // note 1

        // note 2
        if(value >= v1){
            v3 = v2; v2 = v1; v1 = value;
            k3 = k2; k2 = k1; k1 = key;
        }else if(value >= v2){
            v3 = v2; v2 = value;
            k3 = k2; k2 = key;
        }else if(value >= v3){
            v3 = value;
            k3 = key;
        }
    };

    // O(n)
    for(var key in obj){
        // note 3
        insertKey(key);
    }

    return [k1, k2, k3];
}

https://jsfiddle.net/DerekL/pzatq729/

Please do not copy-paste the code right into your homework as your solution. Rewrite the code once you fully understand it.

Note:

1. This assumes that object lookup is O(1). This ultimately depends on how it is implemented in the interpreter, but it is usually lower than O(log n).
2. These conditionals can certainly be optimized. I will leave that as a practice for the reader.
3. Normally we should check if the key is owned by the object instance, but here I will assume that the input object is not inherited from Object.prototype.