Moore Voting Algorithm | LeetCode |169. Majority Element

Problem:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Intuition:

The intuition for this problem is a bit challenging. Understanding the problem. we have an array of length n that contains an element that occurs more than n/2 times in the array. Looking at the problem it means we need to iterate each element of the array, store the occurrence of each element, and then check which element satisfies the condition.

Brute-Force Solution:

The brute-force solution could be having a nested for loop where the “i” loop picks an element and the “j” loop counts the occurrence. After each “i” interaction we check the occurrence with the condition if the condition is true we return the value. Else the “i” loop goes on till the end of the array.

def majorityElemmentBruteForce( nums: List[int]) -> int:
    ans  = 0
    n = len(nums)
    for i in range(0, n):
        count = 0
        for j in range(0, n):
            if(nums[i] == nums[j]):
                count +=1
        if(count > n//2):
            ans = nums[i]
        return ans
    return ans

The time complexity for this solution is O(n²). While the space complexity is O(1).

Better Solution:

The better solution for this is with the help of a two-pass algorithm. we can create a dictionary with the key being the element and the value being the occurrence. In the first iteration, we can generate the data in the dictionary. where in each iteration we check if the value already exists in the dictionary, if this is the case we increase the value by one. else we add a new entry.

once the first iteration is completed we then, iterate the dictionary and check the value of each key against the condition. if the condition is resolved we return the value.

def majorityElemmentBetter( nums: List[int]) -> int:
    ans  = 0
    hash_table = dict()
    for i in range(0,len(nums)):
        if(nums[i] in hash_table):
            hash_table[nums[i]] += 1
        else:
            hash_table[nums[i]] = 1
    for k,h in hash_table.items():
        if(h > len(nums)//2):
            ans = k
    return ans

the time complexity for this solution is O(2n). where the space complexity is O(n).

Optimal Solution:

The optimal solution for this problem is with the help of the Moore Voting algorithm. This algorithm states that. take a count variable and a candidate variable assign the first element of the array to the candidate and increment the count with 1. Now we consider that the first element is the value we need. we start the iteration on each interaction we check if the value is the same as the candidate we increment the count but if the value is different we decrease the count. If the count reaches 0 we then change the candidate to the value on which the count has become 0 and increment the count with 1.

When votes become 0, this actually means that there are an equal number of votes for different elements, which should not be the case for the element to be the majority element. So the candidate element cannot be the majority and hence we choose the present element as the candidate and continue the same till all the elements get finished. The final candidate would be our majority element. We check using the 2nd traversal to see whether its count is greater than N/2. If it is true, we consider it as the majority element.

def majorityElemmentOptimal( nums: List[int]) -> int:
    candidate = nums[0]
    counter = 1

    for i in range(1,len(nums)):
        if(nums[i] == candidate):
            counter +=1
        else:
            counter -= 1
        if(counter == 0):
            candidate = nums[i]
            counter = 1
    return candidate

the time complexity for this algorithm is O(n). And space complexity is O(1).