Majority Element¶

A majority element in an array A[] of size n is an element that appears more than n/2 times
and hence there is at most one such element

[3 3 4 2 4 4 2 4 4] => 4
[3 3 4 2 4 4 2 4] => None

Using Dictionary: O(n) - O(Distinct(n))¶

In [1]:

def findMajorityElement(arr):
    dict = {}
    
    for a in arr:
        if a not in dict:
            dict[a] = 0
        
        dict[a] += 1
        if dict[a] > (len(arr) / 2):
            return a
        
    return 'None'

In [2]:

arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
arr

Out[2]:

[3, 3, 4, 2, 4, 4, 2, 4, 4]

In [3]:

findMajorityElement(arr)

Out[3]:

In [4]:

arr = [3, 3, 4, 2, 4, 2, 4]
arr

Out[4]:

[3, 3, 4, 2, 4, 2, 4]

In [5]:

findMajorityElement(arr)

Out[5]:

'None'

Moore's Voting Algo: O(n)¶

This is a two step process.

The first step gives the element that may be majority element in the array
Check if the element obtained from above step is majority element

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

In [6]:

def chooseOne(arr):
    chosen_index = 0
    count = 1
    
    for i in range(1, len(arr)):
        if arr[chosen_index] == arr[i]:
            count += 1
        else:
            count -= 1
            
        if count == 0:
            chosen_index = i
            count = 1
    
    return arr[chosen_index] if isMajority(arr, arr[chosen_index]) else 'None'

In [7]:

def isMajority(arr, chosenOne):
    count = 0
    
    for a in arr:
        if chosenOne == a:
            count += 1
    
    if count > (len(arr) / 2):
        return True
    else:
        return False

In [8]:

arr = [3, 3, 4, 2, 4, 4, 2, 4, 4]
arr

Out[8]:

[3, 3, 4, 2, 4, 4, 2, 4, 4]

In [9]:

chooseOne(arr)

Out[9]:

In [10]:

arr = [3, 3, 4, 2, 4, 2, 4]
arr

Out[10]:

[3, 3, 4, 2, 4, 2, 4]

In [11]:

chooseOne(arr)

Out[11]:

'None'