Is there a O(n) way to find the most repeated item in list without using counter

I need a solution that is O(n) for finding most repeated element in a list. If 2 or more numbers are repeated the same amount of time return smallest number.

from collections import Counter
 
def most_frequent(n):
    count_occurence = Counter(n)
    return count_occurence.most_common(1)[0][0]

input = [2,4,4,5,2,3,3,4,5,6,6,6,1]

Output should be 4 which should give the count of 3

Answer

You could use max and groupby:

from itertools import groupby

def most_frequent(li):
    maxes=[]
    for k,g in groupby(sorted(li)):
        maxes.append((len(list(g)), -k))
        
    return -max(maxes)[1]

Or use a dict as a counter:

def most_frequent(li):
    cnt={}
    for e in li:
        cnt[-e]=cnt.get(-e, 0)+1
    
    return -max(cnt.items(), key=lambda t: (t[1],t[0]))[0]

Or if your data has runs of similar numbers, without the O(n log n) sort step you can combine these two methods:

def most_frequent(li):
    cnt={}
    for k,g in groupby(li):
        cnt[-k]=cnt.get(-k,0)+len(list(g))
        
    return -max(cnt.items(), key=lambda t: (t[1],t[0]))[0]

And it likely is the case that using max on a comprehension is faster than using a lambda:

def most_frequent(li):
    cnt={}
    for k,g in groupby(li):
        cnt[-k]=cnt.get(-k,0)+len(list(g))
                
    return -max(((y,x) for x,y in cnt.items()))[1]

In all cases, you are construction a tuple of (-element_in_list, count_of_that_element):

cnt=[(-2, 2), (-4, 3), (-5, 2), (-3, 2), (-6, 3), (-1, 1)]

You then take that max of that by reversing the tuple either with a comprehension of a key function. Your answer then is -element_in_list since it was negated to take the max.