Boyer Moore’s Voting Algorithm -Majority Element Leet code Problem Java

Neeraja Gandla
3 min readJul 16, 2020

--

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

Example 1:

Input: [3,2,3]
Output: 3
Input: [2,2,1,1,1,2,2]
Output: 2

You may assume that the array is non-empty and the majority element always exist in the array.

The reference to the problem is here. One way to solve this problem would be to count occurrences of each element using 2 nested loops and use a majorityCount variable to track the maximum among those occurrences. The time complexity of this algorithm would be O(n²). The space complexity would be O(1) since we’re not using any extra space.

A space-time tradeoff approach would be to build a frequency map using a HashMap to store occurrences of each element. At the end pick the element with the highest count. The time complexity of this algorithm would be O(n) since, we are using only one loop at a time. The space complexity would be O(n) since we are using a HashMap to store the frequency.

Is there a way we can solve it in O(n) time complexity and O(1) space complexity? Take some time and think about it.

Think of this problem as vote counting problem. There are several political parties. Each of the parties got a certain number of votes. Assume that each number represents a party. Assume that there’s always a party which gets majority votes-because it’s mentioned in the problem that a majority element always exists. For a party to win by majority, it should get more than half of the total votes cast. For the votes cast to a specific party, each vote is nullified by any vote that’s cast to a different party. The votes of the party which are not nullified by any other parties’ votes contribute to the majority.

Suppose there are 2 parties and 10 people cast the votes. Of those 10 people, let’s say party A got 4 votes and party B got 6 votes. For the first 4 votes of party B, there are also 4 votes cast to party A. So they can be considered to be nullified. The remaining 2 votes decide the winner to be party B. Hence, party B won against party A by 2 votes.

Transferring the same intuition to solve our problem:

Start by assuming that the first element of the array is the majority element. Have a counter variable to count its frequency. As you traverse through the array, if the current element of the array is same as the majority element, increment the counter variable and move ahead. If the current element is not same as the majority element, you need to nullify one vote of the majority element. So, decrement the counter variable if the counter is not already 0. If the counter is zero, reset the majority element to the current element and increment the counter. You will end up with the majority element once the iteration is done. Keep doing this for the entire elements of the array. The code is given below:

public int majorityElement(int[] nums) {
int majority = nums[0], counter = 1;
for(int i = 1; i < nums.length; i++) {
if(counter == 0) {
majority = nums[i];
count = 1;
} else if(nums[i] == majority) counter++;
else counter--;
}
return majority;
}

The time complexity of the algorithm is O(n) and Space Complexity is O(1) or constant space because we did not use any extra space.

My intention to write this blog post is to make the intuition clear regarding the voting algorithm. Please feel free to leave a comment if something is not clear from the post or if it could be improved in any way.

You can find a similar problem for practice on leetcode:

Happy Learning! Cheers!

--

--

Neeraja Gandla

I’m an Android App Developer by Profession. I would like to write out my thoughts and learning to let others learn through my experiences.