1
\$\begingroup\$

I got this interview problem from leetcode for top k frequent elements, https://leetcode.com/problems/top-k-frequent-elements/description/ But I decide to simplify the problem just most common elements to make it simpler to solve. If the 3 item has the same frequentcy, then it's okay to return all 3.

"""Given an array, return an array of the top 2 most elements. // Input: [1, 2, 3, 4, 5, 3, 4] | Output: [3, 4] // Input: [2, 2, 3, 2, 4, 3, 4] | Output: [2,4]"""   

import collections

def top2Frequent(nums):
    """
    :type nums: List[int]
    :type k: int
    :rtype: List[int]
    """
    if len(nums) < 2:
        return []
    freq = {}
    for num in nums:
        if num in freq:
            freq[num] = freq[num] + 1
        else:
            freq[num] = 1

    bucket = collections.defaultdict(list)
    for key in freq:
        f = freq[key]
        bucket[f].append(key)
    res = []
    count = len(nums)  # the upper limit for res
    while len(res) < 2:
        if bucket[count]:
            res += bucket[count]
        count -= 1
    return res


nums = [1, 4, 3, 4, 5, 3, 4]  # [4,3]
solution = top2Frequent(nums)
print(solution) # [4,3]

https://gist.github.com/Jeffchiucp/2e733e57476bd697bc430cdf48f6e180

I am also tried to solve this problem without using any python library built in collections.

\$\endgroup\$
  • 3
    \$\begingroup\$ I'm confused, you say you don't want to use the built-in collections, but you used collections.defaultdict. \$\endgroup\$ – Peilonrayz Jul 23 '18 at 15:39
  • \$\begingroup\$ I don't think the code works as required, when I use nums = [2, 2, 3, 3, 3, 4, 4, 5] the result is [3, 2, 4]. Please fix this before people can answer the question, see also"If your question contains broken code…". \$\endgroup\$ – Jan Kuiken Jul 23 '18 at 16:37
4
\$\begingroup\$

If you're okay with using the built-in collections module, I'd suggest the following. collections.Counter is ideally suited for this and will make the problem trivial.

from collections import Counter


def top_k(numbers, k=2):
    """The counter.most_common([k]) method works
    in the following way:
    >>> Counter('abracadabra').most_common(3)  
    [('a', 5), ('r', 2), ('b', 2)]
    """

    c = Counter(numbers)
    most_common = [key for key, val in c.most_common(k)]

    return most_common

Without using the built-in collections module, the following will work:

def top_k_nobuiltin(numbers, k=2):
    # The first part is identical to your implementation and works just
    # fine
    counter = {}
    for number in numbers:
        if number in counter:
            counter[number] += 1
        else:
            counter[number] = 1

    # The line below creates an iterator that will generate the
    # sequence [(4, 3), (3, 2), (5, 1), (1, 1)], i.e.
    # count the occurrence for each value.
    # In particular, sorted() with key=lambda kv: kv[1] will turn
    # a dictionary into a list of tuples, sorted by the second item
    # of each tuple

    sorted_by_value = reversed(sorted(counter.items(), key=lambda kv: kv[1]))

    top_vals = [item[0] for item in sorted_by_value][:k]

    return top_vals 

For both cases, you'll get the desired result:

def main():
    nums = [1, 4, 3, 4, 5, 3, 4]  # [4,3]

    print(top_k(nums))  # [4,3]
    print(top_k_nobuiltin(nums))  # [4,3]    

if __name__ == '__main__':
    main()
\$\endgroup\$
  • 2
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. \$\endgroup\$ – Toby Speight Jul 23 '18 at 17:08
  • 1
    \$\begingroup\$ @TobySpeight I think that the justification for this answer was self-evident. \$\endgroup\$ – 200_success Jul 23 '18 at 17:55
  • 1
    \$\begingroup\$ I think this solutions violate the must be better than O(n log n) time complexity requirement. \$\endgroup\$ – RandomDude Jul 23 '18 at 18:25
  • 1
    \$\begingroup\$ I totally agree, hadn't read the leetcode description behind the link. Great answer @RandomDude ! \$\endgroup\$ – Daniel Lenz Jul 23 '18 at 19:22
4
\$\begingroup\$

According to the leetcode description one requirement of the algorithm is:

...must be better than O(n log n), where n is the array's size.

I am not 100% sure but i think you can't use the built-in sorted method of python since it has a time complexity of O(n log n). One possibility for this problem is a bucket sort approach.

The idea:

  1. Count frequency of elements in list.
  2. Create a list of buckets with len(nums) + 1 length
  3. Iterate over the frequency dict and put elements in buckets according to their frequency
  4. Iterate in reversed order over the bucket list and return k first elements.
    def top_k_frequent(nums, k):
        cnt = {}
        for n in nums:
            cnt[n] = cnt.get(n, 0) + 1
    
        bucket = [[] for _ in range(len(nums)+1)]    
        for key, val in cnt.items():
            bucket[val].append(key)
    
        res = []
        for i in reversed(range(len(bucket))):
            if bucket[i]:
                res.extend(bucket[i])
            if len(res) >= k:
                break
    
        return res[:k]
    

    Please also see the more elegant approach to count with dict in python.

    \$\endgroup\$

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.