# My understanding of Boyer-Moore Majority Vote

• This problem is an extension to 169. Majority Element, which needs Boyer-Moore Majority Vote Algorithm to find the element, whose count is over `n/2`.

When I was learning about Boyer-Moore, I was always thinking about the pair. I drew a picture to get myself understandable.

Suppose there are nine elements in array A, and the round one is the majority.

No matter in what order we select element from the array, we can only get two results

Compared to fully pairing, it is a little wasting of the partially pairing as there are some round ones are not paired (definitely it would be left). So, under the condition that the majority element exists, we could only think about the fully pairing situation. (It's useful when dealing with `n/3` situation)

We can consider either column as the candidate, and it's intuitive for me to get understand that the code means found a pair.

``````if candidate != element
count -= 1
end
``````

So here comes the `n/3` problem, we would only think about the fully pairing situation. If the over one third majority exists, it should be left after pairing.

Why would we use three elements as a pair? Because it makes sure that in fully pairing the count of majority element equals `n/3`.

That's my understanding about Boyer-Moore. Maybe it's not so clear, but it helps me think about it.

Code

``````# Modified Boyer-Moore Majority Voting Algorithm
def majority_element(nums)
candidate1, candidate2 = 0, 0
count1, count2 = 0, 0

# first round to find candidates
nums.each do |num|
if candidate1 == num
count1 += 1

elsif candidate2 == num
count2 += 1

elsif count1 == 0
candidate1 = num
count1 += 1

elsif count2 == 0
candidate2 = num
count2 += 1

else
# This condition is important, which means a pair out,
# filtering a set of three elements out

count1 -= 1
count2 -= 1
end
end

# second round to confirm
result = []
[candidate1, candidate2].uniq.each do |candidate|
result << candidate if nums.count(candidate) > (nums.count/3)
end

result
end
``````

Reference

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.