Easier Interview Question

my two solutions, second pretty similar to yours.

ls = [6, 8, 1, 1, 2, 3, 8, 5, 5, 8, 8, 8, 8, 8, 8, 8] ls = [1, 1, 2] ls = [] ls = [2, 2, 2, 1, 1, 3, 2, 2] ls = [1, 3, 2, 2, 4, 5]

def majority_element_v0(lst):

if len(lst) == 0:
    return []

lst_dic = [(val, key) for key, val in list(enumerate(lst))]

dic = defaultdict(list)

for key, val in lst_dic:
    dic[key].append(val)

res = [[key, val] for key, val in dic.items() if len(val) > floor(len(lst) / 2)]

if len(res) == 0:
    return []
else:
    return res[0]

print(majority_element_v0(ls))

def majority_element_v1(lst):

if len(lst) == 0:
    return []

m_elem = [key for key, val in Counter(lst).items() if val > floor(len(lst) / 2)]

if len(m_elem) == 0:
    return []

return [m_elem[0], [i for i in range(len(lst)) if lst[i] == m_elem[0]]]

print(majority_element_v1(ls))

Hi @AlexSch thank you for sharing! Great way to use list comprehensions. There are definitely many ways to do this and as long as you comment your code and the interviewer can follow your solution (and the runtime is reasonable/optimal), you’re good to go!

Hello fellows, Here is my solution, I hope it is right:

from collections import Counter

def majority_element_indexes(lst):
    '''
    >>> majority_element_indexes([1,1,2])
    [0, 1]
    >>> majority_element_indexes([1,2])
    []
    >>> majority_element_indexes([])
    []
    >>> majority_element_indexes([1,1,2,2,2,2])
    [2, 3, 4, 5]
    >>> majority_element_indexes([6, 8, 1, 1, 2, 3, 8, 5, 5, 8, 8, 8, 8, 8, 8, 8])
    [1, 6, 9, 10, 11, 12, 13, 14, 15]
    >>> majority_element_indexes([2, 2, 2, 1, 1, 3, 2, 2])
    [0, 1, 2, 6, 7]
    >>> majority_element_indexes([1, 3, 2, 2, 4, 5])
    []
    '''

    n = len(lst) // 2
    cnt = Counter(lst)
    return [index for index, element in enumerate(lst) if cnt[element] > n]

@belushkin it looks right!

For anyone while we upload video descriptions, I talk about Big-O analysis which is a way to analyze the speed and memory usage of a function or block of code. See Wikipedia Time complexity for more information.

Didn’t understand why you flipped - sign for the key fcn.

Hey, here is my solution, which should run O(n) in worst case scenario

from collections import defaultdict


def majority_element_indexes(lst):
    majority_count = len(lst) // 2
    elm_dict = defaultdict(list)
    for i, v in enumerate(lst):
        elm_dict[v] += [i]
        if len(elm_dict[v]) > majority_count:
            return elm_dict[v]
    return []

Hi @Pygator I flipped the sign because by default the sort method sorts in ascending order (so [1, 2, 3]) but in my head I wanted the largest element at the front. However you are right I could have accessed it just with [-1] instead.

@danielzlacky great concise solution without using Counter!

Thanks for the great course! Here is my solution. I used the most_common method of the Counter instance. Hopefully the method was implemented in a smart way so that it runs in O(n) when passing the argument 1.

from collections import Counter

def majority_element_indexes(lst):
    """
    Return a list of indexes of the majority element.
    Majority element is the element that appears more than floor(n / 2) times.
    If there is no majority element, return [].
    >>> majority_element_indexes([1, 1, 2])
    [0, 1]
    >>> majority_element_indexes([1, 2])
    []
    >>> majority_element_indexes([])
    []
    """
    if lst:
        most_frequent_elem, n = Counter(lst).most_common(1)[0]
        if n > len(lst) // 2:
            return [k for k, x in enumerate(lst) if x == most_frequent_elem]
    return []

You said yourself that the the floor calculation constrains the majority element. Since we just want the index of where the majority elements appear in the input, I don’t see the point of finding the max number of occurrences. Or actually determinine what the majority element is. This whole exercise is just a one-liner:

print([i for i, v in enumerate(lst) if Counter(lst)[v] > len(lst)//2])

@Marcus Reaiche great solution and using the built in Counter methods.

@rickfencl That is a cool one line solution! I would probably not come up with that during an actual interview, and also you want to make sure that your interviewer can follow the logic.

As Pythonic as it gets. The idea is to create a defaultdict with a list as a value and append to the list the frequencies and the indices. Then filter out on frequencies and return only the indices.

def major_element(nums):
    if len(nums) == 0: return []
    if len(nums) == 1: return [0]
    thr = len(nums) // 2
    d = defaultdict(list)
    for n_ix in range(len(nums)):
        if nums[n_ix] not in d:
            d[nums[n_ix]].append(1)
            d[nums[n_ix]].append([n_ix])
        else:
            d[nums[n_ix]][0] += 1
            d[nums[n_ix]][1].extend([n_ix])
    return [v[1] if v[0] > thr else [] for k,v in d.items()][0]

Hi, is it right solution?

return [x for x in range(len(lst)) if lst.count(lst[x]) > len(lst) / 2]

Great comments! They took me down a rabbit hole =D

The one liners were fun, but when I checked them out more closely they are both at least O(n^2) right?

Marcus’s solution was the fastest when I used a list of 128000 values. It surprised me that it was all that much faster than danielzlacky’s since they’re both O(n). They seemed to be the same speed when running only 2000 values but Marcus’s pulled away pretty well once the length of the list increased significantly. I also like how concise and easy to read his solution is.

Some observations I got from diving on this exercise:

1. count() appears faster than Counter but if the solution calls count() more than ~5 times Counter seems to be better. If I knew my data was only 2-3 of the same values repeating count() might offer a small performance advantage, but more unique values make Counter come out on top.

2. count() is pretty significantly faster than trying to implement a Python loop that does the same thing. This made me abandon trying to take advantage of some kind of short circuit approach to stop counting and return [] when it’s clear there won’t be enough of any value. From Googling it the reason seems to be because count() uses C which is quite a bit faster than Python.

3. enumerate() and other generators are O(1) to call: it took me 0ns to make an enumerate object regardless of the data size. This was unintuitive for me at first, but made sense after I thought more about what a generator is. Iterating over the resulting generator adds the time complexity. This highlighted to me that I should probably use the tools that result in a generator to iterate across something where possible rather than make a new list or dict using a list comprehension. Or use () instead of [] or {} when doing the comprehension, which makes a generator. I’ll be paying more attention when that scenario comes up in the future.

Hello James! Thanks for your great content.

I wrote a test that does not pass using your solution, e.g.:

Failed example:
majority_element_indexes([1, 1, 2, 3, 1, 4, 4, 4, 4])
Expected:
[5, 6, 7, 8]
Got:
[]

I did an implementation that probably is not the O(n) complexity (actually idk how to measure this), but at least it works for more use cases, here it is:

maj_indexes = []
if(math.floor((len(lst) - 1) / 2) == 0):
    return []
else:
    # var with majority number and how many times it is in lst
    maj_elem = Counter(lst).most_common(1)
    for i, x in enumerate(lst):
        if(maj_elem[0][0] == x):
            maj_indexes.append(i)
return maj_indexes

My solution. From what I gather fairly simillar to ones already posted.

def major_element_indexes(lst):
    if not lst: return []
    counted = Counter(lst)
    threshold = len(lst) // 2
    return [i for i, v in enumerate(lst) if counted[v] > threshold]

Also there is the question : is the majority element one that satisfies the condition of count > len(lst) // 2 or one that has the most occurences in the list ? These are two different cases, I think.

def majority_element_indexes(lst):
    counter = Counter(lst)
    l = [i for i in range(len(lst)) if counter[lst[i]] > len(lst) // 2]
    return l

Hello, I’ve landed to this solution. It works for the three doctest lists, but I don’t really know if it works for every list. Can you have more than one majority element?

Best Regards

Hi there. I am posting my solution here. Please let me know if it is wrong.

def majority_element_index(lst):
    newLst = []
    for i, k in enumerate(lst):
        if lst.count(k) > (len(lst)//2):
            newLst.append(i)
    return newLst

Hi James,

The description says:

def majority_element_indexes(lst):
    '''
    Return a list of the indexes of the majority element.
    Majority element is the element that appears more than
    floor(n / 2) times.
    If there is no majority element, return []
    >>> majority_element_indexes([1, 1, 2])
    [0, 1]

For test case majority_element_indexes([1, 1, 2]), should it return [0] instead of [0, 1] because element "2" does not appear more than floor(n/2) times? Thanks.

Hi James,

Could we use:

top_elem = max(count.keys(), key=lambda x: count[x])  # O(n)

Instead of:

    top_count = max(count.values()) # O(n)
    maj = [
        elen for elem, count
        in count.items if count == top_count
    ][0] # O(n)

Full code:

from collections import Counter
def majority_elements_indexes(lst):
    """
    Return a list of the indexes of the majority element.
    Majority element is the element that appears more than
    floor(n/2) times.
    If there is no majority element, return []
    >>> majority_elements_indexes([1, 1, 2])
    [0, 1]
    >>> majority_elements_indexes([1, 2])
    []
    >>> majority_elements_indexes([])
    []
    """
    # Find majority element
    # if there is no majority element, return []
    # find the indexes fo the majority element,
    # put them in a list
    if len(lst) == 0:
        return []

    count = Counter(lst)  # O(n)
    # top_elem = sorted(count.keys(), key=lambda x: -count[x])[0]  # O(nlogn)
    top_elem = max(count.keys(), key=lambda x: count[x])  # O(n)
    if count[top_elem] > len(lst) // 2:
        return [idx for idx, el in enumerate(lst) if el == top_elem]  # O(n)
    else:
        return []

Thanks bro! I finally feel like I am off the beginner-intermediate plateau and finally moving forward again. Quick question, how does one know when they can rate themselves as an intermediate programmer or an advanced programmer? Thanks again.