# Python solution with detailed explanation

• Solution

Boyer Moore

``````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)
``````

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