How to find a majority element in an Unsorted List in Python

In this tutorial, we will see how to find a majority element from an unsorted list using Python. Here, the definition of the majority element will be defined below in the problem statement.

Problem Statement for finding Majority element from an unsorted list in Python

A list is given as an input that is not sorted. We have to find the majority element. Here majority element is the element that appears more than half the value of list size.

i.e,  an element whose frequency is more than (len(list)/2) times.

Here I am assuming the list is non-empty and the majority element will always exist in the list.

Example:

Input – [2 , 3 , 2 , 2 , 4]

Output – 2

Explanation:- because its frequency is more than (5/2 = 2.5) as len(list) = 5.

We will use simple operations to solve this problem. This problem can be solve using extra space and also without using extra space. But, the more efficient solution will be the one without using extra spaces. So I will discuss that approach and solution i.e without using extra spaces.

You guys can try this question using extra spaces that will also help in developing the logic in different ways.

Code for the given problem :

def maj(LIST):
    if(len(LIST) == 1):     # if length of LIST is 1 then half of length is 0 (int) so LIST[0] is OUTPUT since its frequency is 1>0
        return(LIST[0])
    LIST.sort()            # sorting the LIST in ascending order
    count=1;            
    n = len(LIST)/2        # finding half of length of LIST
    for i in range(0,len(LIST)-1):     
        if(i == len(LIST)-2):        # this condition will check for every LIST[-1] and LIST[-2] elements for every LIST
            if(LIST[i] == LIST[i+1]):
                count = count+1          # incrementing the value if same value 
            if(count>n): 
                return(LIST[i])
        elif(LIST[i] == LIST[i+1]):
            count = count+1          # incrementing the frequency if same value 
        elif(LIST[i] != LIST[i+1]):
            if(count>n):           # checking frequency of a element is greater than n or not
                return(LIST[i])
            else:
                count=1            # if not greater than n then again assign count = 1 and if loop not completed again start the same work via loop
print(maj([2,1,2,2,4]))
print(maj([1]))
print(maj([1,2]))
print(maj([1,1]))

2
1
None
1

Hope this tutorial helps you to understand the concept of this problem statement.

As I mentioned before trying to solve this problem using extra space also.Comment below if you like this content and also you can give me any suggestions regarding this tutorial.

Also read: Python List and Basic Python Set method