Find the majority element, which appears more than half the time 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 =&gt; lst.reduce((acc, x) =&gt; {
  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] &lt; acc[x]) { acc.major = [x, acc[x]]; }
  return acc;
}, {major: null}).major[0];

console.log(findMajorityElem(lst));
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.