SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Boyer-Moore Majority Vote Visualizer

Pair every vote for the candidate with a vote against it, and cancel them. Whatever survives all the cancelling must be the majority, because it has more votes than everything else combined.

Start the Boyer-Moore Majority Vote simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. No candidate yet and count = 0. [2, 2, 1, 1, 1, 2, 2]
  2. count is 0, so 2 becomes the new candidate. Earlier votes have cancelled out.
  3. 2 matches the candidate. count = 1.
  4. 2 matches the candidate. count = 2.
  5. 1 is not 2: it cancels one vote. count = 1.
  6. 1 is not 2: it cancels one vote. count = 0.
  7. count is 0, so 1 becomes the new candidate. Earlier votes have cancelled out.
  8. 1 matches the candidate. count = 1.
  9. 2 is not 1: it cancels one vote. count = 0.
  10. count is 0, so 2 becomes the new candidate. Earlier votes have cancelled out.
  11. 2 matches the candidate. count = 1.
  12. The survivor is 2. It fills 4 of 7 slots, more than half.

Try it with your own input →

Boyer-Moore majority vote in Java, Python, C++, C and JavaScript

int majorityElement(int[] a) {
  int candidate = 0, count = 0;
  for (int x : a) {
    if (count == 0) candidate = x;
    count += (x == candidate) ? 1 : -1;
  }
  return candidate;
}
def majority_element(a):
    candidate, count = 0, 0
    for x in a:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate
int majorityElement(const vector<int>& a) {
  int candidate = 0, count = 0;
  for (int x : a) {
    if (count == 0) candidate = x;
    count += (x == candidate) ? 1 : -1;
  }
  return candidate;
}
int majorityElement(int a[], int n) {
  int candidate = 0, count = 0;
  for (int i = 0; i < n; i++) {
    if (count == 0) candidate = a[i];
    count += (a[i] == candidate) ? 1 : -1;
  }
  return candidate;
}
function majorityElement(a) {
  let candidate = 0, count = 0;
  for (const x of a) {
    if (count === 0) candidate = x;
    count += (x === candidate) ? 1 : -1;
  }
  return candidate;
}

In an interview

LeetCode 169, Majority Element: the value that appears more than n / 2 times. The follow-up is 229 Majority Element II (more than n / 3).

The vote only finds a candidate. If the majority is not guaranteed, make a second pass to count it. A hash map of counts also works but needs O(n) space.

More patterns