# C++ solution using Moore's voting algorithm - O(n) runtime comlexity an no extra array or hash table

• This can be solved by Moore's voting algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. Below code loops through each element and maintains a count of the element that has the potential of being the majority element. If next element is same then increments the count, otherwise decrements the count. If the count reaches 0 then update the potential index to the current element and sets count to 1.

``````int majorityElement(vector<int> &num) {
int majorityIndex = 0;
for (int count = 1, i = 1; i < num.size(); i++) {
num[majorityIndex] == num[i] ? count++ : count--;
if (count == 0) {
majorityIndex = i;
count = 1;
}
}

return num[majorityIndex];
}``````

• Your answer is perfect. However, I want to learn more about the Moore's voting algorithm you mentioned. Can you share any website of the algorithm to me? Thanks a lot.

• Here is a step by step illustrative example from the original author.

• BTW, the efficiency can be improved further by updating the loop condition as follows: "for (int count = 1, i = 1; i < num.size() && count <= num.size(); i++) {". This will allow a possible early exit as soon as we figure out that the count of an occurrence is more than half of the total number of elements in the array.

• great but it requires some knowledge of voting algorithm beforehand....

• bboczeng, you are right it needs the prior knowledge of the voting algorithm. At the same time anyone who is asking this question is not really looking for a brute force method answer. :) I think the idea of this forum is to share such ideas and algorithms so the members are more aware and smatter? :)

• Here is a very helpful blog I found clearly explaining how the Moore's voting algorithm works. It also shows a way to run it in parallel.

http://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

• This is very helpful! The parallel part is amazing

• thx a lot! It is really save space and time!

• A python version. Thanks a lot for sharing the idea.

``````class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):

if not num:
return None

selectedElement = num[0]
count = 0
total = len(num)

for n in num:
if count > total/2:
return selectedElement

if n == selectedElement:
count +=1
elif count == 1:
selectedElement = n
else:
count -= 1

return selectedElement
``````

• shouldn't it be "count <= num.size() / 2" if intend to improve?

• This post is deleted!

• Not sure if it works with this input : 1,1,3,3,3,9,1,9,9,3, the answer I get with the above algo is 9 whereas it should be 3.

• Please read the question carefully, your input {1,1,3,3,3,9,1,9,9,3} is invalid. The question said "The majority element is the element that appears more than ⌊ n/2 ⌋ times." However, your input only contains four 3, while the size of the set is 10. 4 < 10/2. So it has a "wrong" answer. In fact, in this case, it has no correct answer.

• Its actually the following assumption in the question : You may assume that the array is non-empty and the majority element always exist in the array actually which makes the input wrong, bcoz otherwise, we would need to make sure that the element num[majorityIndex] would be > n/2 .

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