**Solution**

**Boyer Moore**

- Linear Pass Algorithm - http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html
- This algorithm assumes that there is a majority element. If we are not sure, we should do one more scan to be certain of this fact.
- Here is another cool explanation of the idea behind this algorithm: https://discuss.leetcode.com/topic/17564/boyer-moore-majority-vote-algorithm-and-my-elaboration/2
- The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as "4 X being paired out by 4 Y".

```
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
counter, candidate = 0, None
for c in nums:
if counter == 0:
counter,candidate = 1, c
elif c == candidate:
counter = counter + 1
else:
counter = counter - 1
return candidate
```

There are several other algorithms. These are explained here: https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations

**HashTable Solution**

- Do an early exit if a solution is found

```
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
counter, N, result = {}, len(nums), None
for c in nums:
if c in counter:
counter[c] = counter[c] + 1
else:
counter[c] = 1
if counter[c] > N//2:
result = c
break
return result
```

**Sorting Based Solution**

- Just sort the array and return N//2 element.

```
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
return nums[len(nums)//2]
```

**Randomized Algorithm**

- Best case O(N) and worst case O(N^2)

```
from random import randint
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
while True:
count,idx = 0, randint(0, len(nums)-1)
for c in nums:
if c == nums[idx]:
count = count + 1
if count >= len(nums)//2 + 1:
return nums[idx]
return
```

**Divide and Conquer**

- The majority element is either the majority in left or right side. Recursively find the solution for left and right and test it out.

```
class Solution(object):
def majorityElement_divide_conquer(self, nums, low, high):
"""
:type nums: List[int]
:rtype: int
"""
if low == high:
return nums[low]
mid = low + int((high-low)/2)
lm = self.majorityElement_divide_conquer(nums, low, mid)
rm = self.majorityElement_divide_conquer(nums, mid+1, high)
if lm == rm:
return lm
lcount,rcount = nums[low:high+1].count(lm), nums[low:high+1].count(rm)
return lm if lcount > rcount else rm
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return self.majorityElement_divide_conquer(nums, 0, len(nums)-1)
```