# Get the Most frequent element in an array

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));

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?

• To clarify, what do you mean by “mode”? The statistical zero-th moment of a distribution? Jul 12, 2021 at 13:37
• The element that is repeated the most in the array Jul 12, 2021 at 13:39
• You've said "trying to optimize". Did you profile the code? What did you get? Anyway, it should be clear that sorting to get the maximum is a bad idea. Jul 12, 2021 at 14:16
• Do you want to improve speed or memory usage? Jul 13, 2021 at 9:18

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))

• Yeah... @PavloSlavynskyy... thanks for correcting! Jul 12, 2021 at 14:22
• @PavloSlavynskyy according to this (stackoverflow.com/questions/33611509/…) discussion in V8 JavaScript Engine the time complexity of retrieval and lookup is O(1) Jul 12, 2021 at 15:02

## 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.

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))