Majority Element in a List

Solution using Moore’s Voting Algorithm

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        current = nums[0]
        freq = 1
        
        for i in range(1, len(nums)):
            if current is None:
                current = nums[i]
                freq = 1
                continue
                
            if nums[i] == current:
                freq += 1
            else:
                freq -= 1
            
            if freq == 0:
                current = None
                
        return current

The idea assumes that a majority element do exist in the list. Each unique element cancels out each other and the last standing element is the answer.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: