Boyer–Moore major­ity vote algorithm. In its sim­plest form, the algo­rithm finds a major­ity ele­ment, if there is one: that is, an ele­ment that occurs repeat­edly for more than half of the ele­ments of the input. How­ever, if there is no major­ity, the algo­rithm will not detect that fact, and will still out­put one of the ele­ments. A ver­si…

boyer-moore.js

// Majority vote algorithm
// Objective: Given an array of integer, write an algorithm to find the majority element in it (if exist)
// Majority element: If an element appears more than n / 2 times in array where n is the size of the array
function BoyerMoore () {
  let i = 0
  let m
  return {
    vote (x) {
      if (i === 0) {
        m = x
        i = 1
      } else if (m === x) {
        i += 1
      } else {
        i -= 1
      }
      return m
    },
    score (arr) {
      return {
        isMajority: arr.filter(v => v === m).length > arr.length / 2,
        majority: m
      }
    }
  }
}

const boyerMoore = BoyerMoore()
// const arr = [1, 1, 1, 3, 3, 2, 2, 3, 3, 3, 2, 3, 3]
const arr = ['a', 'a', 'a', 'c', 'c', 'b', 'b', 'c', 'c', 'c', 'b', 'c', 'c']
arr.forEach(boyerMoore.vote)
console.log(boyerMoore.score(arr))