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.

This is absolutely no different from finding the Top k elements in an array — Bergi
– Bergi, Commented Aug 17, 2017 at 23:35

Dij · Accepted Answer · 2017-08-17 23:46:33Z

2

you can keep pushing 3 objects in an array and keep sorting the array, assuming number of elements you need k is sufficiently less than n, this can give linear efficiency on average.

let objToCheck = {
  a: 2, 
  b: 5,
  c: 9,
  d: 33,
  e: 4,
  f: 8,
  g: 3,
  h: 10
};


function findBig3(obj){
  var res = [-1,-1,-1];

  for (let key in obj){
   res[3] = obj[key];
   res.sort(function(a,b){return b-a});
  }
  res.pop();
  return res;
}


console.log(findBig3(objToCheck));

edited Aug 17, 2017 at 23:46

answered Aug 17, 2017 at 23:30

Dij

9,8184 gold badges21 silver badges35 bronze badges

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

2 Comments

Derek 朕會功夫 Over a year ago

We can also create an array with 4 elements and always put the newest one at the end to avoid calling .push and .pop.

Dij Over a year ago

@Derek朕會功夫 yeah that would be better, thanks for suggestion, code updated.

Derek 朕會功夫 · Accepted Answer · 2017-08-17 23:32:40Z

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:

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).
These conditionals can certainly be optimized. I will leave that as a practice for the reader.
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.

spanky · Accepted Answer · 2017-08-17 23:15:43Z

0

If you just change Object.values to Object.keys and use the key to select from the original object, you can avoid the last loop.

let objToCheck = {
  a: 2,
  b: 5,
  c: 9,
  d: 33,
  e: 4,
  f: 8,
  g: 3,
  h: 10
};

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

console.log(findBig3(objToCheck));

answered Aug 17, 2017 at 23:15

spanky

2,86010 silver badges9 bronze badges

1 Comment

Derek 朕會功夫 Over a year ago

.sort is not O(n).

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related