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