CA 21 - Find the Majority Element

Problem Statement: here

Solution:

• The method keeps track of current element and count.
• The current element is the value being followed at that moment.
• Count shows how many times that value is being supported compared to other values.
• While moving through the array if the same element appears again, the count increases or if a different element appears, the count decreases.
• This decrease means different elements are canceling each other out.
• When the count becomes 0, the previous current element has lost all support and a new current element is chosen.
• At the end, the remaining current element is the only possible majority element.
• After that, count how many times this element appears in the array. If it appears more than half the size of the array, return it, otherwise return -1.

def majorityElement(arr):
    current = None
    count = 0
    for num in arr:
        if count == 0:
            current = num
        if num == current:
            count += 1
        else:
            count -= 1
    if arr.count(current) > len(arr) // 2:
        return current
    return -1