Majority Element Problem

Problem Introduction

Given a sequence of $n$ elements, suppose that one element $a$ occurs strictly more than $n/2$ times. Find this element.

Methods

Offline Algorithm

If the entire sequence is known from the beginning, a natural approach is to count the occurrences of every element. The element occurring more than $n/2$ times is the majority element. We can create a bucket to count the occurrences of each value and output the one whose count exceeds $n/2$.

However, introducing a bucket is not ideal in terms of space efficiency. Clearly, if a sequence has a majority element, then after sorting, its $\lfloor n/2\rfloor+1$-th element must be the majority element. We can find this element with nth_element. Thus, without using extra space, we find the majority element in linear time.

Online Algorithm

In some situations, we need to process streaming data online. We then need an algorithm that does not know all the data in advance but gradually obtains the answer using only the data currently provided. The majority vote algorithm ¹ solves the majority-element problem online.

Because the majority element occurs more than $n/2$ times, in a complete sequence, repeatedly canceling one majority element with one element different from it must leave the majority element at the end. Based on this observation, we can design an online algorithm that performs these cancellations. Let val and cnt represent the current majority candidate and the number of copies the candidate would have after these cancellations so far. Initially, set cnt to $0$. Each time an element is read from the stream, if cnt is $0$, the previous candidate has been completely canceled, so the recorded val cannot be the majority; the current element becomes the new candidate. We then check whether the current element is the candidate. If it is, increment cnt by $1$; otherwise, it is canceled together with one candidate, so decrement cnt by $1$. Repeating this until the stream is exhausted leaves val equal to the majority element.

Example Problems

#include <cstdio>

int main() {
  int n;
  scanf("%d", &n);
  int val, cnt = 0;
  while (n--) {
    int x;
    scanf("%d", &x);
    if (!cnt) val = x;
    (val == x) ? ++cnt : --cnt;
  }
  printf("%d\n", val);
  return 0;
}

class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    // Change the majority vote algorithm from “cancel two different elements” to “cancel three pairwise different elements”
    int maj1, maj2;
    int cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
      if (num == maj1) {
        ++cnt1;
      } else if (num == maj2) {
        ++cnt2;
      } else if (cnt1 == 0) {
        maj1 = num;
        ++cnt1;
      } else if (cnt2 == 0) {
        maj2 = num;
        ++cnt2;
      } else {
        --cnt1;
        --cnt2;
      }
    }

    // The problem does not guarantee two elements occur more than ⌊ n/3 ⌋ times, so the candidates must be checked
    vector<int> ans;
    cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
      if (num == maj1)
        ++cnt1;
      else if (num == maj2)
        ++cnt2;
    }
    int n = nums.size();
    if (cnt1 > n / 3) ans.push_back(maj1);
    if (cnt2 > n / 3) ans.push_back(maj2);

    return ans;
  }
};

References