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

Question

The task:

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

Answer 1

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.

Answer 2

@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, 
  converge( reduce(maxBy(last)), [head, identity] ),
  head, 
  parseInt
)(lst)

You can try it here

Answer 3

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