7
$\begingroup$

Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space.

The intuition behind finding the majority element is understandable as it has to be greater than the count of other elements in the input sequence if a majority element exists.

However, there is a variation of this algorithm to find the elements occurring more than [n / 3] where n is the length of the sequence.

The algorithm goes like this.

  • Start with two empty candidate slots and two counters set to 0.
  • for each item:
    • if it is equal to either candidate, increment the corresponding count
    • else if there is an empty slot (i.e. a slot with count 0), put it in that slot and set the count to 1
    • else reduce both counters by 1

I can understand there will be at most (n /3) - 1 entries so we keep two containers and their counts.

But I'm not sure why the last reduce both by 1 is pivotal to this algorithm. I would be very helpful if you explain the intuition behind this.

Code of the above algorithm

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{ // This part
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Algorithm and code source

$\endgroup$
  • $\begingroup$ If there were two values accounting for two thirds of the elements, the counts would be about zero. (When refining the title to give a clue to the variation, check its first word.) $\endgroup$ – greybeard May 12 '18 at 6:27
  • $\begingroup$ But I'm not sure why the last reduce both by 1 is pivotal to this algorithm. In other words, you are not sure why the algorithm works at all. You are looking for a proof that the algorithm is correct. $\endgroup$ – Yuval Filmus May 12 '18 at 9:01
  • $\begingroup$ You can also try changing this step and checking whether the new algorithm still works. You will probably be able to find a counterexample. $\endgroup$ – Yuval Filmus May 12 '18 at 9:01
13
$\begingroup$

Here is a different way to consider the same algorithm, or rather its general form with $k$ counters (in your case, $k=2$). There are $k$ "containers" and a trash bag. Each container will contain one type of element at a time. Initially everything is empty. When we read a new element $x$, we consider the following cases:

  • If there is a container containing $x$'s, add $x$ to that container.
  • If there is no container containing $x$ and there is an empty container, put $x$ in the empty container.
  • If there is no container containing $x$ and there are no empty containers, remove one element from each container, and put $x$ in the trash.

When the algorithm terminates, each of the $n$ elements is either found in one of the $k$ containers, or in the trash bag.

Suppose that element $x$, not found in any of the containers, is found $m$ times in the input. Thus all $m$ copies of $x$ are in the trash bag. Each time an element is put in the trash bag, $k$ other elements are also put in the trash bag together with it. This means that the trash bag contains at least $(k+1)m$ elements, and so $(k+1)m \leq n$ or $m \leq n/(k+1)$.

Consequently, if an element appears more than $n/(k+1)$ times in the input then it will necessarily be found in one the $k$ containers. In other words, the algorithm correctly identifies all elements appearing more than $n/(k+1)$ times.

Note how this analysis crucially depends on the fact that when trashing $x$ in the third case above, we also trash $k$ additional elements together with it.

$\endgroup$
  • $\begingroup$ Just to be sure I understand correctly: if all $k$ containers are taken, the element $x$ will go into the trash, but since every time we put an $x$ into the trash we put one element from the containers as well. Since $x$ appears more than $n/(k+1)$ times in the input, eventually one of the containers will become empty, and subsequent $x$ elements will go into that container. Is this correct? $\endgroup$ – Katona Jan 30 '20 at 16:27
  • $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus Jan 30 '20 at 16:28
  • $\begingroup$ Very smart, I am in awe :) How one finds such an algorithm is beyond me. $\endgroup$ – Katona Jan 30 '20 at 16:39
  • $\begingroup$ The general form can produce false positives so you better re-check the output. E.g., [1,2,1] => 1 finds empty cell, 2 finds empty cell, 1 increments. [1,2] returned while 2 count is not > 1 ! $\endgroup$ – BitWhistler Nov 26 '20 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.