Find the most common element in a list

Question

What is an efficient way to find the most common element in a Python list?

My list items may not be hashable so can't use a dictionary. Also in case of draws the item with the lowest index should be returned. Example:

>>> most_common(['duck', 'duck', 'goose'])
'duck'
>>> most_common(['goose', 'duck', 'duck', 'goose'])
'goose'

Krakau

If the items in the list are not hashable, how would you determine when they are 'equal'? The efficiency loss in determining equality for non-hashable items would probably negate any efficiency you hope to gain with a good algorithm :) – Sapid

I think he means that the items can be mutable and thus not elegible to be keys in a hashmap... – Nostology

yeah that's what I meant - sometimes it will contain lists – Krakau

Related: Finding the most common element in a list, but without the special requirement in case of a tie – Delamination

Answer 1

With so many solutions proposed, I'm amazed nobody's proposed what I'd consider an obvious one (for non-hashable but comparable elements) -- [itertools.groupby][1]. itertools offers fast, reusable functionality, and lets you delegate some tricky logic to well-tested standard library components. Consider for example:

import itertools
import operator

def most_common(L):
  # get an iterable of (item, iterable) pairs
  SL = sorted((x, i) for i, x in enumerate(L))
  # print 'SL:', SL
  groups = itertools.groupby(SL, key=operator.itemgetter(0))
  # auxiliary function to get "quality" for an item
  def _auxfun(g):
    item, iterable = g
    count = 0
    min_index = len(L)
    for _, where in iterable:
      count += 1
      min_index = min(min_index, where)
    # print 'item %r, count %r, minind %r' % (item, count, min_index)
    return count, -min_index
  # pick the highest-count/earliest item
  return max(groups, key=_auxfun)[0]

This could be written more concisely, of course, but I'm aiming for maximal clarity. The two print statements can be uncommented to better see the machinery in action; for example, with prints uncommented:

print most_common(['goose', 'duck', 'duck', 'goose'])

emits:

SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]
item 'duck', count 2, minind 1
item 'goose', count 2, minind 0
goose

As you see, SL is a list of pairs, each pair an item followed by the item's index in the original list (to implement the key condition that, if the "most common" items with the same highest count are > 1, the result must be the earliest-occurring one).

groupby groups by the item only (via operator.itemgetter). The auxiliary function, called once per grouping during the max computation, receives and internally unpacks a group - a tuple with two items (item, iterable) where the iterable's items are also two-item tuples, (item, original index) [[the items of SL]].

Then the auxiliary function uses a loop to determine both the count of entries in the group's iterable, and the minimum original index; it returns those as combined "quality key", with the min index sign-changed so the max operation will consider "better" those items that occurred earlier in the original list.

This code could be much simpler if it worried a little less about big-O issues in time and space, e.g....:

def most_common(L):
  groups = itertools.groupby(sorted(L))
  def _auxfun((item, iterable)):
    return len(list(iterable)), -L.index(item)
  return max(groups, key=_auxfun)[0]

same basic idea, just expressed more simply and compactly... but, alas, an extra O(N) auxiliary space (to embody the groups' iterables to lists) and O(N squared) time (to get the L.index of every item). While premature optimization is the root of all evil in programming, deliberately picking an O(N squared) approach when an O(N log N) one is available just goes too much against the grain of scalability!-)

Finally, for those who prefer "oneliners" to clarity and performance, a bonus 1-liner version with suitably mangled names:-).

from itertools import groupby as g
def most_common_oneliner(L):
  return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]

Joanjoana

This breaks on Python3 if your list has different types. – Brierwood

groupby requires sorting first (O(NlogN)); using a Counter() with most_common() can beat that because it uses a heapq to find the highest frequency item (for just 1 item, that's O(N) time). As Counter() now is heavily optimised (counting takes place in a C loop), it can easily beat this solution even for small lists. It blows it out of the water for large lists. – Septet

Only the 'lowest index' requirement for ties makes this a valid solution for just this problem. For the more general case you definitely should use the Counter approach. – Septet

@MartijnPieters Perhaps you've missed the part of the question where it said the items may be unhashable. – Leibniz

@Leibniz right, and if items are unhashable. Which makes the votes on the set and max approach all the more incongruous. – Septet

@AlexMartelli why complicate things when we have simplicity of python? Please check https://mcmap.net/q/109287/-find-the-most-common-element-in-a-list – Streetlight

@BreakBadSP: Your/newacct's solution is simple, but highly inefficient for large inputs. It's O(nm) where n is total elements and m is unique elements, and still requires hashable elements (omitting set to work with non-hashable, it's O(n²)), where this solution is O(n log n) and doesn't require hashable (just sortable) elements, and Alex's solution is O(n) (requiring hashable elements, but benefiting meaningfully from it). If your input is small, it doesn't matter, but if you've got 10M elements, it makes a big difference. – Devoirs

Answer 2

A simpler one-liner:

def most_common(lst):
    return max(set(lst), key=lst.count)

Immediately

The OP stated that [..] in case of draws the item with the lowest index should be returned. This code does not, in general, meet that requirement. – Shanteshantee

Plus, the OP stated that the elements must be hashable: sets must contains hashable objects. – Nyssa

Plus, this approach is algorithmically slow (for each elements in set(lst), the whole list must be checked again)… Probably fast enough for most uses, though… – Nyssa

You can replace set(lst) with lst and it will work with non-hashable elements too; albeit slower. – Immediately

This may look attractive but from an algorithmic point of view this is terrible advice. list.count() has to traverse the list in full, and you do so for every single unique item in the list. This makes this a O(NK) solution (O(N^2) in the worst case). Using a Counter() only takes O(N) time! – Septet

I tried the same but it shows "TypeError: unhashable type: 'list'". How to resolve this? – Biogeochemistry

@shivam: That would happen if lst itself contained sub-lists (because list is mutable/non-hashable, it can't be a member of a set). If you can make it a list of tuples instead (where all the values in the tuples are hashable), it will work. That said, you'd still want to use a Counter-based solution if the input is of meaningful size; this is a O(n²) solution, which requires the input to be a list (or tuple or str) as well, where Counter solutions work on arbitrary iterable inputs (assuming hashable values) and are O(n). – Devoirs

Answer 3

Borrowing from here, this can be used with Python 2.7:

from collections import Counter

def Most_Common(lst):
    data = Counter(lst)
    return data.most_common(1)[0][0]

Works around 4-6 times faster than Alex's solutions, and is 50 times faster than the one-liner proposed by newacct.

On CPython 3.6+ (any Python 3.7+) the above will select the first seen element in case of ties. If you're running on older Python, to retrieve the element that occurs first in the list in case of ties you need to do two passes to preserve order:

# Only needed pre-3.6!
def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)

Ilowell

This might be useful to some but ... unfortunately Counter is a dict subclass, and the OP said he couldn't use dictionaries (as items may not be hashable). – Preston

Love this. The one-liner by @Immediately above may be simple, but it runs in O(n^2); that is, where n is the length of the list. This solution is O(n). – Recension

Like the simplicity and the speed... maybe not ideal for OP. But suits me great! – Fenugreek

doesn't return the lowest indexed item. most_common returns an unordered list, and grabbing (1) just returns whatever it would like. – Applesauce

@AgentBawls: most_common is sorted by count, not unordered. That said, it won't pick the first element in case of ties; I've added another way to use the counter that does pick the first element. – Tauto

Note: As of CPython 3.6 and any version of Python compatible with 3.7 or higher, the original code will work correctly even in case of ties (because dicts and dict subclasses became insertion-ordered as a CPython 3.6 implementation detail, and as a language feature in 3.7). So return Counter(lst).most_common(1)[0][0] (or return max(data, key=data.__getitem__) since it's just one value) will work without a second pass over lst on modern Python. – Devoirs

Answer 4

What you want is known in statistics as mode, and Python of course has a built-in function to do exactly that for you:

>>> from statistics import mode
>>> mode([1, 2, 2, 3, 3, 3, 3, 3, 4, 5, 6, 6, 6])
3

Note that if there is no "most common element" such as cases where the top two are tied, this will raise StatisticsError on Python <=3.7, and on 3.8 onwards it will return the first one encountered.

Submarine

this doesn't satisfy the OP's requirement of what to return when there is more than one most common value - a statistics.StatisticsError is raised – Keg

Oops, missed the requirement when reading it. I still believe this answer holds value though, as no one suggested it in this question, and it is a good solution for the problem for people with least restrictive requirements. This is one of the top results for "most common item in list python" – Submarine

In that case use the mode function in pandas DataFrames. – Reynaud

Up-vote, this one should be higher. And it's not that hard to satisfy the OP's requirement with simple try-except (see my https://mcmap.net/q/109287/-find-the-most-common-element-in-a-list) – Sportive

why need to import statistics only for this https://mcmap.net/q/109287/-find-the-most-common-element-in-a-list – Streetlight

@Streetlight your answer uses more memory because of the additional set, and is plausibly O(n^3). – Submarine

The text in bold is no longer correct. This has been changed in 3.8: Now handles multimodal datasets by returning the first mode encountered. Now statistics.multimode(data) is available – Trinhtrini

Amusingly, the code that implements statistics.mode, aside from converting the exception type, is essentially the same as the code in the old answer using Counter; the implementation is pairs = Counter(iter(data)).most_common(1), then it tries to return pairs[0][0]. The iter` call is to deal with an ambiguity when passed a dict; the function expects only an iterable of values, and if it didn't call iter, dicts would just use their existing key/value pairs to initialize the Counter, rather than counting the keys. – Devoirs

Although it works for number, the original question involved strings – Bespoke

Answer 5

Without the requirement about the lowest index, you can use collections.Counter for this:

from collections import Counter

a = [1936, 2401, 2916, 4761, 9216, 9216, 9604, 9801] 

c = Counter(a)

print(c.most_common(1)) # the one most common element... 2 would mean the 2 most common
[(9216, 2)] # a set containing the element, and it's count in 'a'

Tartuffery

this answer needs more upvotes as it addresses the general task of counting element occurrences in a list using a standard module and 2 lines of code – Kaila

But Counter does throw a TypeError: unhashable type is the list includes unhashable types (as the original question suggested) so it's not a solution here. – Orthman

Answer 6

If they are not hashable, you can sort them and do a single loop over the result counting the items (identical items will be next to each other). But it might be faster to make them hashable and use a dict.

def most_common(lst):
    cur_length = 0
    max_length = 0
    cur_i = 0
    max_i = 0
    cur_item = None
    max_item = None
    for i, item in sorted(enumerate(lst), key=lambda x: x[1]):
        if cur_item is None or cur_item != item:
            if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
                max_length = cur_length
                max_i = cur_i
                max_item = cur_item
            cur_length = 1
            cur_i = i
            cur_item = item
        else:
            cur_length += 1
    if cur_length > max_length or (cur_length == max_length and cur_i < max_i):
        return cur_item
    return max_item

Phototypy

Here's a simpler way ideone.com/Nq81vf , comparing with Alex's Counter() solution – Jerold

Answer 7

This is an O(n) solution.

mydict   = {}
cnt, itm = 0, ''
for item in reversed(lst):
     mydict[item] = mydict.get(item, 0) + 1
     if mydict[item] >= cnt :
         cnt, itm = mydict[item], item

print itm

(reversed is used to make sure that it returns the lowest index item)

Averil

Answer 8

A one-liner:

def most_common (lst):
    return max(((item, lst.count(item)) for item in set(lst)), key=lambda a: a[1])[0]

Piggyback

This is a lot of wrapping to achieve the same end result as newacct's answer's return max(set(lst), key=lst.count); it looks like you're trying to do a decorate-sort-undecorate (aka Schwartzian transform) pattern here (replacing sorting with max), but it's pointless for max (where every element would compute its key only once even without caching involved), and equally unnecessary for sorted/list.sort (where it's doing decorate-sort-undecorate under the hood on your behalf, without an unnecessary genexpr involved). – Devoirs

Answer 9

Sort a copy of the list and find the longest run. You can decorate the list before sorting it with the index of each element, and then choose the run that starts with the lowest index in the case of a tie.

Mcmann

The items may not be comparable. – Nim

Answer 10

I am doing this using scipy stat module and lambda:

import scipy.stats
lst = [1,2,3,4,5,6,7,5]
most_freq_val = lambda x: scipy.stats.mode(x)[0][0]
print(most_freq_val(lst))

Result:

 most_freq_val = 5

Alluring

Answer 11

# use Decorate, Sort, Undecorate to solve the problem

def most_common(iterable):
    # Make a list with tuples: (item, index)
    # The index will be used later to break ties for most common item.
    lst = [(x, i) for i, x in enumerate(iterable)]
    lst.sort()

    # lst_final will also be a list of tuples: (count, index, item)
    # Sorting on this list will find us the most common item, and the index
    # will break ties so the one listed first wins.  Count is negative so
    # largest count will have lowest value and sort first.
    lst_final = []

    # Get an iterator for our new list...
    itr = iter(lst)

    # ...and pop the first tuple off.  Setup current state vars for loop.
    count = 1
    tup = next(itr)
    x_cur, i_cur = tup

    # Loop over sorted list of tuples, counting occurrences of item.
    for tup in itr:
        # Same item again?
        if x_cur == tup[0]:
            # Yes, same item; increment count
            count += 1
        else:
            # No, new item, so write previous current item to lst_final...
            t = (-count, i_cur, x_cur)
            lst_final.append(t)
            # ...and reset current state vars for loop.
            x_cur, i_cur = tup
            count = 1

    # Write final item after loop ends
    t = (-count, i_cur, x_cur)
    lst_final.append(t)

    lst_final.sort()
    answer = lst_final[0][2]

    return answer

print most_common(['x', 'e', 'a', 'e', 'a', 'e', 'e']) # prints 'e'
print most_common(['goose', 'duck', 'duck', 'goose']) # prints 'goose'

Lodie

Answer 12

Building on Luiz's answer, but satisfying the "in case of draws the item with the lowest index should be returned" condition:

from statistics import mode, StatisticsError

def most_common(l):
    try:
        return mode(l)
    except StatisticsError as e:
        # will only return the first element if no unique mode found
        if 'no unique mode' in e.args[0]:
            return l[0]
        # this is for "StatisticsError: no mode for empty data"
        # after calling mode([])
        raise

Example:

>>> most_common(['a', 'b', 'b'])
'b'
>>> most_common([1, 2])
1
>>> most_common([])
StatisticsError: no mode for empty data

Sportive

Answer 13

Simple one line solution

moc= max([(lst.count(chr),chr) for chr in set(lst)])

It will return most frequent element with its frequency.

Eatton

Answer 14

You probably don't need this anymore, but this is what I did for a similar problem. (It looks longer than it is because of the comments.)

itemList = ['hi', 'hi', 'hello', 'bye']

counter = {}
maxItemCount = 0
for item in itemList:
    try:
        # Referencing this will cause a KeyError exception
        # if it doesn't already exist
        counter[item]
        # ... meaning if we get this far it didn't happen so
        # we'll increment
        counter[item] += 1
    except KeyError:
        # If we got a KeyError we need to create the
        # dictionary key
        counter[item] = 1

    # Keep overwriting maxItemCount with the latest number,
    # if it's higher than the existing itemCount
    if counter[item] > maxItemCount:
        maxItemCount = counter[item]
        mostPopularItem = item

print mostPopularItem

Malpractice

you could use counter[item] = counter.get(item, 0) + 1 to replace the try/except part – Tanto

Answer 15

ans  = [1, 1, 0, 0, 1, 1]
all_ans = {ans.count(ans[i]): ans[i] for i in range(len(ans))}
print(all_ans)

all_ans={4: 1, 2: 0}
max_key = max(all_ans.keys())

4

print(all_ans[max_key])

1

Dream

Answer 16

This is the obvious slow solution (O(n^2)) if neither sorting nor hashing is feasible, but equality comparison (==) is available:

def most_common(items):
  if not items:
    raise ValueError
  fitems = [] 
  best_idx = 0
  for item in items:   
    item_missing = True
    i = 0
    for fitem in fitems:  
      if fitem[0] == item:
        fitem[1] += 1
        d = fitem[1] - fitems[best_idx][1]
        if d > 0 or (d == 0 and fitems[best_idx][2] > fitem[2]):
          best_idx = i
        item_missing = False
        break
      i += 1
    if item_missing:
      fitems.append([item, 1, i])
  return items[best_idx]

But making your items hashable or sortable (as recommended by other answers) would almost always make finding the most common element faster if the length of your list (n) is large. O(n) on average with hashing, and O(n*log(n)) at worst for sorting.

Expeller

To the downvoter: what's wrong with this answer? Does any of the other answers provide a solution when neither sorting nor hashing is feasible? – Expeller

Answer 17

Here:

def most_common(l):
    max = 0
    maxitem = None
    for x in set(l):
        count =  l.count(x)
        if count > max:
            max = count
            maxitem = x
    return maxitem

I have a vague feeling there is a method somewhere in the standard library that will give you the count of each element, but I can't find it.

Spies

'max' is a method. Would you change the name of the variable? – Dinka

Note that set() also requires hashable items, to the solution wouldn't work in this case. – Arianearianie

Wait, I missed that part of not being hashable. But if the objects have equality it should be easy to make them hashable. – Spies

Answer 18

>>> li  = ['goose', 'duck', 'duck']

>>> def foo(li):
         st = set(li)
         mx = -1
         for each in st:
             temp = li.count(each):
             if mx < temp:
                 mx = temp 
                 h = each 
         return h

>>> foo(li)
'duck'

Dinka

This has terrible performance characteristic when n is big and the number of unique elements is large as well: O(n) for the conversion to a set and O(m*n)=O(n^2) for the count (where m is the number of uniques). Sort and walk is O(n log n) for the sort and 0(n) for the walk. – Surgeonfish

Yeah you are right. Now I know this is a terrible solution and why. Thanks for comment!! :-) – Dinka

Answer 19

I needed to do this in a recent program. I'll admit it, I couldn't understand Alex's answer, so this is what I ended up with.

def mostPopular(l):
    mpEl=None
    mpIndex=0
    mpCount=0
    curEl=None
    curCount=0
    for i, el in sorted(enumerate(l), key=lambda x: (x[1], x[0]), reverse=True):
        curCount=curCount+1 if el==curEl else 1
        curEl=el
        if curCount>mpCount \
        or (curCount==mpCount and i<mpIndex):
            mpEl=curEl
            mpIndex=i
            mpCount=curCount
    return mpEl, mpCount, mpIndex

I timed it against Alex's solution and it's about 10-15% faster for short lists, but once you go over 100 elements or more (tested up to 200000) it's about 20% slower.

Patchouli

Answer 20

Hi this is a very simple solution, with linear time complexity

L = ['goose', 'duck', 'duck']

def most_common(L):

current_winner = 0
max_repeated = None
for i in L:
    amount_times = L.count(i)
    if amount_times > current_winner:
        current_winner = amount_times
        max_repeated = i

return max_repeated

print(most_common(L))

"duck"

Where number, is the element in the list that repeats most of the time

Forswear

Answer 21

#This will return the list sorted by frequency:

def orderByFrequency(list):

    listUniqueValues = np.unique(list)
    listQty = []
    listOrderedByFrequency = []
    
    for i in range(len(listUniqueValues)):
        listQty.append(list.count(listUniqueValues[i]))
    for i in range(len(listQty)):
        index_bigger = np.argmax(listQty)
        for j in range(listQty[index_bigger]):
            listOrderedByFrequency.append(listUniqueValues[index_bigger])
        listQty[index_bigger] = -1
    return listOrderedByFrequency

#And this will return a list with the most frequent values in a list:

def getMostFrequentValues(list):
    
    if (len(list) <= 1):
        return list
    
    list_most_frequent = []
    list_ordered_by_frequency = orderByFrequency(list)
    
    list_most_frequent.append(list_ordered_by_frequency[0])
    frequency = list_ordered_by_frequency.count(list_ordered_by_frequency[0])
    
    index = 0
    while(index < len(list_ordered_by_frequency)):
        index = index + frequency
        
        if(index < len(list_ordered_by_frequency)):
            testValue = list_ordered_by_frequency[index]
            testValueFrequency = list_ordered_by_frequency.count(testValue)
            
            if (testValueFrequency == frequency):
                list_most_frequent.append(testValue)
            else:
                break    
    
    return list_most_frequent

#tests:
print(getMostFrequentValues([]))
print(getMostFrequentValues([1]))
print(getMostFrequentValues([1,1]))
print(getMostFrequentValues([2,1]))
print(getMostFrequentValues([2,2,1]))
print(getMostFrequentValues([1,2,1,2]))
print(getMostFrequentValues([1,2,1,2,2]))
print(getMostFrequentValues([3,2,3,5,6,3,2,2]))
print(getMostFrequentValues([1,2,2,60,50,3,3,50,3,4,50,4,4,60,60]))

Results:
[]
[1]
[1]
[1, 2]
[2]
[1, 2]
[2]
[2, 3]
[3, 4, 50, 60]

Knurly

Answer 22

def most_frequent(List):

    counter = 0

    num = List[0]

 

    for i in List:

        curr_frequency = List.count(i)

        if(curr_frequency> counter):

            counter = curr_frequency

            num = i


    return num


List = [2, 1, 2, 2, 1, 3]

print(most_frequent(List))

Kurman

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Eleneeleni

Answer 23

numbers = [1, 3, 7, 4, 3, 0, 3, 6, 3]
max_repeat_num = max(numbers, key=numbers.count)     *# which number most* frequently
max_repeat = numbers.count(max_repeat_num)           *#how many times*
print(f" the number {max_repeat_num} is repeated{max_repeat} times")

Hersh

Calling max() with an iterable – Hersh

just a small note, this algorithm is O(n^2) it's not going to be fast compared to the other answers on this question. – Bare

Answer 24

def mostCommonElement(list):
  count = {} // dict holder
  max = 0 // keep track of the count by key
  result = None // holder when count is greater than max
  for i in list:
    if i not in count:
      count[i] = 1
    else:
      count[i] += 1
    if count[i] > max:
      max = count[i]
      result = i
  return result

mostCommonElement(["a","b","a","c"]) -> "a"

Roller

all the other answers. would you like me to link them? – Amathiste

Answer 25

The most common element should be the one which is appearing more than N/2 times in the array where N being the len(array). The below technique will do it in O(n) time complexity, with just consuming O(1) auxiliary space.

from collections import Counter

def majorityElement(arr):        
    majority_elem = Counter(arr)
    size = len(arr)
    for key, val in majority_elem.items():
        if val > size/2:
            return key
    return -1

Dewain

Can't use Counter on lists that contain unhashable elements. – Orthman

Can you suggest a better way buddy @Orthman ? – Dewain

The accepted solution further down does without. – Orthman

Okay thanks @Orthman : ) – Dewain

What about a list like this: [1, 1, 1, 2, 3, 4, 5, 6] the most common element is 1, but it occurs 3 times which is less than N/2 (N=8 in this case). – Tallage

Answer 26

 def most_common(lst):
    if max([lst.count(i)for i in lst]) == 1:
        return False
    else:
        return max(set(lst), key=lst.count)

Recalescence

Please provide some information about your code, just posting code isn't a complete answer – Whimsicality

Is there a reason someone should use this over the 15 other answers? – Sometime

Answer 27

def popular(L):
C={}
for a in L:
    C[a]=L.count(a)
for b in C.keys():
    if C[b]==max(C.values()):
        return b
L=[2,3,5,3,6,3,6,3,6,3,7,467,4,7,4]
print popular(L)

Tseng