Boyer-Moore Voting Algorithm

The Boyer-Moore Voting algorithm is used to find the maximum occurrence of an element provided that the element has occurred more than or equal to half of the array length.

The original research of this algorithm is presented at cs.utexas.edu/~moore/best-ideas/mjrty

The approach is basically straightforward and it relies on the fact that if an element occurs more than 1/2 time then it will contribute the highest in terms of volume.

So we take an element and if the next element will be the same as the taken element we will increase a counter else we will decrease the counter. If we follow this logic then at the end we will get the element that has highest contribution in the volume of the array.

Note: We are not interested in finding the frequency that how many times it has occurred duplicate, we just need to find which element has contributed at the highest in the volume of the array.

Let's understand this approach with the example

We have elements,

[1 1 1 3 3 2 2 3 3 3 2 3 3]

Now, we take the candidate element as the first element and represent it with a count of 1.

Now, we increment the pointer and since the next element is the same as the candidate element we will increase the count.

Now, as you can see the next element is not the 1 and so we decrease the count and move the pointer until the counter does not get 0

So, after three iterations, our count becomes 0. Now, when the count becomes 0 then this is the sign that we need to change our candidate element. Thus, we change the candidate element from 1 to 2. And re-start the count

Now, again since we get the element not the same as the candidate element we will decrease the count and re-instantiate when the count becomes 0

Now, repeating the same procedure after a few iterations we get the 2. So again we decrease the count from 2 to 1 but thereafter again we have 3 so again change from 1 to 2 and at last end up at 3.

Now, we discard the count that is of no use and the candidate element is the element that has occurred more than 1/2 of the times in the array.

The whole code on this logic is as follows:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        candidate = nums[0]
        count = 1

        for i in range(1, len(nums)):
            if nums[i] == candidate:
                count += 1
            elif count == 0:
                candidate = nums[i]
            else:
                count -= 1

        return (candidate)

Thank you for reading my blog! DMs are open connect me at linktr.ee/prituldave