Get the Most frequent element in an array

Question

I have been trying to optimize this:

const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];

const getMode = (arr) => arr
    .sort(
      (a, b) =>
        arr.reduce((acu, cur) => (cur === a ? (acu += 1) : cur)) -
        arr.reduce((acu, cur) => (cur === b ? (acu += 1) : cur))
    )
    .pop();

console.log(getMode(NUMBERS));

I had thought about this too:

const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];

const mode = (arr) => arr
    .sort(
      (a, b) =>
        arr.filter((v) => v === a).length - arr.filter((v) => v === b).length
    )
    .pop();
    
console.log(mode(NUMBERS))

What do you think can be improved?

Answer 1

In order to improve the performance, you can reduce the complexity of the code.

Currently, the complexity of your approaches is O(n² log(n)) as the sort function is O(n log(n)) and in each iteration, you are using filter or reduce which has a complexity of O(n).

I can suggest one approach where you don't need to sort the elements and so the complexity of the method will be O(n) if using V8 JavaScript Engine (for more information) otherwise O(n log(n)). Check out this approach:

const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];

const getMode = (arr) => {

  let [maxFreq, result] = [-1, -1];
        
  arr.reduce((acu, cur) => {
                  acu.set(cur, (acu.has(cur) ? acu.get(cur) : 0)+1)
                  return acu;
                 }, new Map())
            .forEach((value, key) => {
                if(value > maxFreq){
                  maxFreq = value;
                  result = key;
                }
              });
  
  return result;
    
 }

console.log(getMode(NUMBERS))

Answer 2

Sort!

Never use a sort to get a max or min. Sort is only used to order all items in the array.

If you want a max in an array you can use Math.max(...[1,2,3,4,5,6,5,4,3,2]) expresses 6.

If you need an associated value linked to a max or min you will need to iterate manually storing the max and associated data as and when you find new values.

Rewrite

The example tests the count of values against a max max and store both the max count and the value maxVal of the counted value

To count values it uses a map which uses a hash map and is \$O(1)\$ for lookups which will make the function \$O(n)\$

function getMode(data) {
    var max = -Infinity, maxVal, counts = new Map(), c;
    for (const v of data) {
        c = ++(counts.get(v) ?? (counts.set(v, c = {count: 0}), c)).count;
        [max, maxVal] = c > max ? [c, v] : [max, maxVal];
    }
    return maxVal;
}

console.log(getMode([2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9]))

You could also check if max is greater than (n / 2) and exit as if the count is over half the items the value must be the most frequent.

Answer 3

I have modified the answer of the HandsomeCoder.

This is actually O(n) because object access is O(1)

const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];

function getMode(array) {
    function buildFrequencyMap(array) {
        return array.reduce((acu, number) => {
            acu[number] = acu[number] !== undefined ? acu[number] + 1 : 0
            return acu;
        }, {})
    }

    function maxFrequency(frequencyMap) {
        let maxFreq = -1, result = -1

        Object.entries(frequencyMap).forEach(([key, value]) => {
            if(value > maxFreq){
                maxFreq = value;
                result = key;
            }
        });

        return result
    }

    const frequencyMap = buildFrequencyMap(array)

    return maxFrequency(frequencyMap);
}

console.log(getMode(NUMBERS))