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

Tech mentioned