Leetcode 169. Majority Element

Problem Statement 📑

In order to better understand the problem, first we have to know what is majority element and what are the properties of majority element. Any element that appears more than half of times of length of array, then that element is called majority element.

Examples: 
nums= [1,2,2,1,1]  output=1

nums=[-2,1,99,2,2]  output=2

Now we know what is majority element and seen some examples, think about how to solve the problem.

Thought Process 1 : Simple Counter Method 🧠

This is the first approach that comes to mind. As per definition of majority element, Element has to appear more than N/2 times. So maintaining counter will easily solve the problem.

def majority_counter(nums) :
    # simple counter approach. count occurances of all elements 
    # and return ele with count >N /2

    if len(nums) <= 0 :
        return

    counter = {}
    for ele in nums :
        if ele in counter :
            counter[ele] += 1
        else :
            counter[ele] = 1

    # check the counts

    for ele, count in counter.items() :
        if count > len(nums) // 2 :
            return ele
    # Time Complexity: O(N)
    # Space Complexity: O(N)

Even though time complexity is linear, we are also taking linear space to solve this. We are not making use of property of majority element i.e, it will be more than half of elements.

Thought Process 2: Optimal approach 🧠

If we know majority element exists for sure, then there is no need to keep track of counts of all elements. So what we can do is, for every element we increase count if it is majority element and decrement if it is some other element. This approach is also called Boyer Moore voting algorithm.

def majority_BoyerMoore(nums) :

    # this approch only works when there is already majority element in array.
    # idea: since we know majority ele occurs > N/2... we simply track majority ele.
    # if ele is majority, we increment the count otherwise we decrement the count.
    # when count becomes zero, no majority element till now...

    majority = nums[0]   # we init first ele as majority
    count = 1

    for ele in nums[1 : ] :      
        if ele == majority :
            count += 1   # increase the count if it is majority ele        
        elif ele != majority :
            if count == 0 :  # new majority element
                majority = ele
                count = 1             
            else :  
                count -= 1   # decrease the count, if ele is not majority element

    return majority

   # Time Complexity: O(N)
   # Space Complexity: O(1)

If you wish to further read on Boyer Moore algorithm here is the article in wikipedia and Geeks For Geeks

Other approaches:

• Brute Force : Two loops where we count occurrences of each element and return if count of element > N/2
• Sorting: This is also easy to code approach. We just sort all the elements. Since majority element has to be more than N/2 times, the element will be either in first half or second half. Just comparing first, mid and last element will give the required target element. Time complexity for this approach is O(NlogN) and Space is O(1)

Conclusion

Thanks for reading and make sure to practise the problem here leetcode link. As always all the code files will be present in Github. We will meet again with different problem. Until then 👋👋