0

The task is to return the K most frequent elements. What I did is to calculate the frequencies and put it in a min-heap (as we know there's no max-heap in Python), then I need to heappop k times.

from collections import defaultdict
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counts = defaultdict(int)
        for i in range(len(nums)):
            counts[nums[i]] -= 1
            
        counts = list(counts.items())
        heapq.heapify(counts)
        top_k = [heapq.heappop(counts)[0] for i in range(k)]
        return top_k

Why does my code fails on topKFrequent([4,1,-1,2,-1,2,3], 2)?

OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
greenButMellow
  • 316
  • 1
  • 9
  • Whereas it's true that there's no max-heap in Python, you can simulate one easily enough. One suggested way is to negate the values. So 4 becomes -4, etc. Another way to do it is to use a custom compare predicate as described in https://stackoverflow.com/a/8875823/56778 – Jim Mischel Aug 29 '22 at 16:57

1 Answers1

3

You asked why it fails. It's failing because the heappop is returning the smallest item from counts. Counts is a tuple, so it is the smallest by the first element of the tuple, which are the nums. So you are getting back the nums, but only the unique ones because the dictionary is essentially acting like set.

dsagman
  • 481
  • 1
  • 8
  • Also, heapify doesn't allow interaction via a key, so you can't use a lambda to get at the second value of the tuple. Here's a reference. https://stackoverflow.com/questions/45892736/python-heapq-how-do-i-sort-the-heap-using-nth-element-of-the-list-of-lists. – dsagman Aug 28 '22 at 13:49