# Find the majority element, which appears more than half the time

Given a list of elements, find the majority element, which appears more than half the time (> floor(len(lst) / 2.0)).

You can assume that such element exists.

For example, given [1, 2, 1, 1, 3, 4, 0], return 1.

My solution:

const lst = [1, 2, 1, 1, 3, 4, 0];
const findMajorityElem = lst => lst.reduce((acc, x) => {
acc[x] = acc[x] ? acc[x] + 1 : 1;
// If I can assume that such an element exists, then it's sufficient to check which element occurs the most.
if (!acc.major || acc.major[1] < acc[x]) { acc.major = [x, acc[x]]; }
return acc;
}, {major: null}).major[0];

console.log(findMajorityElem(lst));
• In the example [1, 2, 1, 1, 3, 4, 0], 1 appears 3 times, floor(len(lst) / 2.0)) is 3, and since 3 is not more than 3, therefore 1 is not the majority element, and the example list doesn't have a majority element. Commented Apr 1, 2019 at 16:47
• @janos the example is inaccurate. However it explicitly says I can assume that there exists a majority element Commented Apr 1, 2019 at 16:54

If it is known that a majority element exists, then the efficient algorithm to use is the Boyer-Moore majority vote algorithm, which requires only O(1) space.

• That's a little deceptive... it's $\Omega(\log n)$ space in terms of bit complexity. Commented Apr 1, 2019 at 20:44
• @Charles Why would you want to break it down in terms of bits? Commented Apr 2, 2019 at 1:18
• I think the question should be, why hide the size of the space requirements? Calling O(1) is, IMO, deceptive: it makes it sound like a fixed amount of space suffices for arbitrarily large arrays, but the larger the array the larger the numbers you need to store, and the larger the numbers the larger the space they take up. Sure, only logarithmically so, but then let's call it logarithmic space, not constant space. It's only constant space in the sense that you use a constant number of words when the words themselves grow logarithmically, but then you're being tricky and hiding the real size. Commented Apr 2, 2019 at 1:59
• @Charles I don't understand why there's necessarily a correlation between the size of the array and the size of the values within it. To me those are completely orthogonal concerns. It also doesn't seem particularly relevant here anyway, since Javascript's numbers are fixed-size.
– Kyle
Commented Apr 2, 2019 at 2:31
• @Charles I don’t think that’s entirely fair. Unlike algorithms and structures that meaningfully depend on bit width (radix sort, van Emde Boas trees, ...), this one only has a dependence on it in that it needs to store an array index and an array element (an offline version can also get away with storing two indices instead). That is, it needs as much space as an array access, and you generally want to count this as O(1). Yes, that means you’re counting words, not bits, but that’s the standard cost model, and it makes perfect sense outside of specialized applications. Commented Apr 2, 2019 at 14:17

@200_success's suggestion seems like the right play here.

That said, I thought it was worth pointing out a couple small improvements to your approach:

• major need only be the element itself (since you can look up its value in the accumulator)
• Since you tagged this functional-programming, you can use expressions everywhere, and avoid the if statement.

Revised code:

const findMajorityElem = lst => lst.reduce((acc, x) => {
acc[x] = acc[x] ? acc[x] + 1 : 1;
const maxCnt = acc[acc.major] || 0
acc.major = acc[x] <= maxCnt ? acc.major : x
return acc
}, {major: null}).major

And just for fun, again based on your tag, here's a single-expression solution in Ramda. Again, I don't recommend actually using this given that Boyer-Moore exists:

pipe(
groupBy(identity),
map(length),
toPairs,
parseInt
)(lst)

You can try it here

If the number exists, it should be done like this and shorter.

let result =
[2,3,4,5,1,1,1,2,2,22,2,2,2,2,2,2,2,2,1,1,33,3,2,1,1,1,1,2,2,2,2,2].reduce( (a ,b) => {
console.log(a)
return a.length == null  ? ( a != b ?  [] : a.concat(b)):
a.length == 0  ? [b] :
a[a.length-1] == b ?  a.concat(b)  :
a.slice(0,a.length-2) ;
})[0]

console.log(result) //2
• Welcome to Code Review! and shorter is a bit short on what deserves improvement in the code in the question and why the way proposed is better. Commented Apr 2, 2019 at 5:42
• Shorter means in Javascript, you may write in a neater way. It’s an implementation of voter algorithm. Just compare the last element in result with a new element, if they are different, just cancel them. Then the final survived element will be the result. Time is o(n) and if in-place space is o(1). Commented Apr 2, 2019 at 11:41