Top K Frequent Elements

Leetcode Problem 347: Top K Frequent Elements

Problem Summary

Given an integer array nums and an integer k, find and return the k elements that appear most frequently in the array. The answer is guaranteed to be unique (no ambiguity for the k-th slot) and can be returned in any order.

Constraints:

• The array can have up to 100,000 elements, each in the range [−10,000, 10,000].
• k is between 1 and the number of distinct elements in the array.
• The answer is always unique — there is no tie for the k-th most frequent element.

Follow up: Your algorithm's time complexity must be better than O(n log n).

nums = [1, 1, 1, 2, 2, 3],  k = 2

Frequency count:         Top k=2 most frequent:
  1 → ███  (3 times)     [1, 2]
  2 → ██   (2 times)
  3 → █    (1 time)

Techniques

• Array
• Hash Table
• Divide and Conquer
• Sorting
• Heap (Priority Queue)
• Bucket Sort
• Counting
• Quickselect

Solution

import { Heap } from "../heap"

function topKFrequent(nums: number[], k: number): number[] {
    const kFrequentElements = new Heap<{ element: number, frequency: number}>(
        (a, b) => a.frequency - b.frequency
    )
    const frequencies = new Map<number, number>()

    for (const num of nums) {
        frequencies.set(num, (frequencies.get(num) || 0) + 1)
    }

    for (const [element, frequency] of frequencies) {
        kFrequentElements.insert({ element, frequency })
        
        if (kFrequentElements.size() > k) {
            kFrequentElements.extract()
        }
    }

    const result: number[] = []

    while (kFrequentElements.size() > 0) {
        result.push(kFrequentElements.extract()!.element)
    }

    return result
}

console.log(topKFrequent([1,2,1,2,1,2,3,1,3,2], 2)) // Output: [1,2]