Katkat
Back

Find K most frequent elements

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to combine frequency maps with selection algorithms or heap-based structures to efficiently identify top-k elements.

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Function Signature

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= number of unique elements in the array

Examples

Example 1:

  • Input: nums = [1,1,1,2,2,3], k = 2
  • Output: [1, 2]
  • Explanation: The frequency of 1 is 3, 2 is 2, and 3 is 1. The top 2 elements are 1 and 2.

Example 2:

  • Input: nums = [1], k = 1
  • Output: [1]

Edge Cases

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

Requirements

Your algorithm's time complexity must be better than O(N log N), where N is the number of elements in the array.

Hints

Hint 1

Start by counting the occurrences of each element using a hash map.

Hint 2

Consider using a min-heap to keep track of the top k elements while iterating through the frequency map.

Hint 3

Alternatively, can you achieve O(N) time complexity using a bucket-sort approach where the index represents the frequency?

Follow-up questions

  • How would your approach change if you were asked to find the k least frequent elements instead?
  • If the data were provided as a stream (infinitely large input), how would you maintain the top k elements without storing the full history?
  • What is the memory footprint of your solution, and can you optimize the space complexity if the range of numbers is very small?