AlgoDaily 06: Majority Element
https://algodaily.com/challenges/majority-element
“Suppose we’re given an array of numbers like the following:
[4, 2, 4]Could you find the majority element? A majority is defined as “the greater part, or more than half, of the total. It is a subset of a set consisting of more than half of the set’s elements.
Let’s assume that the array length is always at least one, and that there’s always a majority element.
In the example above, the majority element would be 4.”
Seems like a hash would work for this:
function majorityElement(items) {
const counts = {};
let maxCount = 0;
let majorityElement;
for (const item of items) {
if (!(item in counts)) {
counts[item] = 0;
}
counts[item]++;
if (counts[item] >= Math.floor(items.length / 2) && counts[item] > maxCount) {
majorityElement = item;
}
}
return majorityElement;
}
Test cases:
majorityElement([1, 4, 2, 4, 4, 3, 4]);
// 4
majorityElement([1, 1, 1, 4, 2, 4, 4, 3, 1, 1, 1]);
// 1
This is a brute-force approach but is straightforward.
Algo Daily has an interesting solution: sort the items, then take the median item, as a majority item is guaranteed to be at this index in a sorted array:
function majorityElement(items) {
return items.sort()[Math.floor(items.length / 2)];
}