What is Boyer-Moore Voting Algorithm?
The Boyer-Moore Voting Algorithm is a highly efficient way to find the majority element in an array in linear time $O(n)$ and constant space $O(1)$.
Boyer-Moore Voting Algorithm (Simple analogy in my own word)
Imagine you have a notebook where you’re tracking everyone’s shirt colour at a party. Each time you see a new colour, you write it down and give it a count of 1. If you see the same colour again, you increase the count.
If you see a different colour, you decrease the count. Eventually, when the count reaches zero, it’s like saying, “I’ve paired off this colour with other colours enough times, now I’ll start fresh.” At this point, you reset the colour to whatever you’re seeing now and set the count to 1 again.
By the time you’ve gone through the whole crowd, you’ll have eliminated all the “balanced/matched” pairs of colours. The colour left standing with the positive count is the one that showed up the most—it is the majority colour.
Code Implementation (JS)
1/**
2 * @param {number[]} nums
3 * @return {number}
4 */
5var majorityElement = function (nums) {
6 let N = nums.length
7 let major = nums[0];
8 let count = 1;
9
10 for (let i = 1; i < N; i++) { // Starts with 2nd element
11 if (count === 0) {
12 major = nums[i];
13 count = 1;
14 } else if (major === nums[i]) {
15 count++;
16 } else {
17 count--;
18 }
19 }
20
21 return major;
22};
Example Walkthroughs
Example 1
1Input: [3, 2, 3]
2Initial candidate: 3, count: 1
3
4Step 1: (nums[1] = 2)
5- Current candidate: 3, count: 0
6- Update: new candidate = 2, count = 1
7
8Step 2: (nums[2] = 3)
9- Current candidate: 2, count: 0
10- Update: new candidate = 3, count = 1
11
12Final candidate: 3 (Majority element)
Example 2
1Input: [2, 2, 1, 1, 1, 2, 2]
2Initial candidate: 2, count: 1
3
4Step 1: (nums[1] = 2)
5- Current candidate: 2, count: 2
6
7Step 2: (nums[2] = 1)
8- Current candidate: 2, count: 1
9
10Step 3: (nums[3] = 1)
11- Current candidate: 2, count: 0
12- Update: new candidate = 1, count = 1
13
14Step 4: (nums[4] = 1)
15- Current candidate: 1, count: 2
16
17Step 5: (nums[5] = 2)
18- Current candidate: 1, count: 1
19
20Step 6: (nums[6] = 2)
21- Current candidate: 1, count: 0
22- Update: new candidate = 2, count = 1
23
24Final candidate: 2 (Majority element)
Example 3
1Input: [1]
2Initial candidate: 1, count: 1
3
4Since the array has only one element, it is trivially the majority element.
5
6Final candidate: 1 (Majority element)
Example 4
1Input: [6, 5, 5, 6, 6]
2Initial candidate: 6, count: 1
3
4Step 1: (nums[1] = 5)
5- Current candidate: 6, count: 0
6- Update: new candidate = 5, count = 1
7
8Step 2: (nums[2] = 5)
9- Current candidate: 5, count: 2
10
11Step 3: (nums[3] = 6)
12- Current candidate: 5, count: 1
13
14Step 4: (nums[4] = 6)
15- Current candidate: 5, count: 0
16- Update: new candidate = 6, count = 1
17
18Final candidate: 6 (Majority element)