Friedrich Ewald My Personal Website

Leetcode: Top k frequent elements

Given a list nums and a positive integer k, return the top k frequent items from the list. A time complexity constraint is not given for this task. The task can be broken down into two problems. First, identifying the most frequent items and then returning them. For the first part, I used a simple map to count the occurrences. Afterwards, I iterated over the map and flipped the key and value around in a tuple. If for example the number 10 occurred 5 times, the corresponding tuple would be (5, 10). With this structure I was able to use the heapq package in Python. This library uses the first element of a tuple to determine the order of elements. As his library creates by default a min heap and we are interested in the maximum elements, we can simply make the values negative. This puts the most frequent elements at the top of the heap.

import heapq
from typing import List, Optional

class Solution:
  def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    # Count all occurences
    m = {}
    for n in nums:
      if n not in m:
        m[n] = 0
      m[n] += 1
    l = []
    for key, v in m.items():
    output = []
    for _ in range(k):

    return output

if __name__ == '__main__':
  s = Solution().topKFrequent
  print(s([1,1,1,2,2,3], 2), [1,2])
Runtime: 227 ms, faster than 14.08% of Python3 online submissions for Top K Frequent Elements. Memory Usage: 18.7 MB, less than 71.72% of Python3 online submissions for Top K Frequent Elements.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.