CODEWITHSUNDEEP
pythonheap
greenButMellow
greenButMellow

Reputation: 338

return top K frequent elements

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)?

Upvotes: 0

Views: 313

Answers (1)

dsagman
dsagman

Reputation: 491

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.

Upvotes: 3

Related Questions