Introduction

Do you have an opportunity to find the majority in constant space? The Boyer-Moore Majority Vote Algorithm works for it.

Problem Statement

N people vote for one of 0 ~ N-1 to elect a leader. Find all people who received more than 1/3 of the total votes. However, implement it with time complexity O(N) and space complexity O(1).

How it works

First, we can see that at most 2 people can receive more than 1/3 of the total votes. Therefore, we execute the first loop to find 2 potential candidates. Each candidate counts their own votes, but the key point of this algorithm is that when a vote goes to someone else, that count decreases by 1. Since the count can decrease, it may become 0, in which case the candidate is no longer a special candidate. They become an ordinary person like everyone else. So the next person who receives a vote becomes the next candidate. By repeating this, we can see that the person who remains a candidate until the end is the one who received the most votes. However, they may not necessarily have received more than 1/3 of the total votes, so we count the candidates’ votes and verify.

The following code finds the elements that appear more than n//3 times where n is the number of all elements.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        
        count1, count2 = 0, 0
        candidate1, candidate2 = 0, 1

        for n in nums:
            if candidate1 == n:
                count1 += 1
            elif candidate2 == n:
                count2 += 1
            else:
                if count1 == 0:
                    candidate1 = n
                    count1 += 1
                elif count2 == 0:
                    candidate2 = n
                    count2 += 1
                else:
                    count1 -= 1
                    count2 -= 1
        
        # verify candidates
        x = len(nums) // 3

        count1, count2 = 0, 0
        for n in nums:
            if n == candidate1:
                count1 += 1
            elif n == candidate2:
                count2 += 1
        
        ans = []
        if x < count1:
            ans.append(candidate1)
        
        if x < count2:
            ans.append(candidate2)
        
        return ans

Reference

Majority Voting Algorithm