Katkat
Back

Find top-k distinct elements

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to combine frequency counting with heap-based selection to extract the k most frequent distinct elements from an input stream.

Problem Statement

Given an array of integers nums and an integer k, return the k most frequent elements in the array. You may return the answer in any order, but the elements must be distinct.

Constraints

  • 1 <= nums.length <= 10^5
  • nums[i] is between -10^4 and 10^4.
  • k is in the range [1, number of unique elements in the array].
  • The result is guaranteed to be unique.

Function Signature

def top_k_frequent(nums: list[int], k: int) -> list[int]:

Examples

Example 1: Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] Explanation: 1 appears three times, 2 appears two times, and 3 appears one time. The top 2 are 1 and 2.

Example 2: Input: nums = [1], k = 1 Output: [1]

Edge Cases

  • The array contains only one unique element.
  • All elements have the same frequency.
  • k is equal to the total number of unique elements.

Hints

Hint 1

Use a hash map to store the frequency of each element in the input array.

Hint 2

Once you have the frequencies, consider using a min-heap of size k to keep track of the elements with the highest frequencies.

Hint 3

Alternatively, you can use bucket sort logic where the index represents the frequency, allowing for linear time complexity relative to the number of elements.

Follow-up questions

  • How would you optimize this if the input array is massive and cannot fit into memory?
  • What is the time and space complexity of your solution, and can you achieve better than O(N log k) time?
  • If the frequencies were updated in real-time, how would your data structure choice change to maintain the top-k efficiently?