Problem of The Day: Top K Frequent Elements

2 min read 545 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        min_heap = []
        counter = Counter(nums)
        for key, value in counter.items():
            heapq.heappush(min_heap, [value, key])
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return [x for _, x in min_heap]

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var minHeap = new PriorityQueue<(int,int), int>();
        var freq = new Dictionary<int, int>();
        foreach(var num in nums) {
            freq[num] = freq.GetValueOrDefault(num) + 1;
        }

        Console.WriteLine(string.Join(", ", freq.Select(kvp => "[" + kvp.Key + ", " + kvp.Value + "]")));

        foreach(var (key, val) in freq) {
            minHeap.Enqueue((val, key), val);
            if (minHeap.Count > k) {
                minHeap.Dequeue();
            }
        }
        var result = new List<int>();
        while (minHeap.Count > 0) {
            var (key, value) = minHeap.Dequeue();
            result.Add(value);
        }
        return result.ToArray();
    }
}

• time: O(N log k)
• space: O(k)

Editorial

Approach 1: Heap

from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # O(1) time
        if k == len(nums):
            return nums

        # 1. Build hash map: character and how often it appears
        # O(N) time
        count = Counter(nums)
        # 2-3. Build heap of top k frequent elements and
        # convert it into an output array
        # O(N log k) time
        return heapq.nlargest(k, count.keys(), key=count.get)