Katkat
Back

Return the Top K Most Frequent Elements

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to efficiently count element frequencies and use bucket-based sorting to avoid O(N log N) time complexity.

Problem Statement

Given an array of integers nums and an integer k, return the k most frequent elements. If two or more elements have the same frequency, the element that appeared first in the original input array should be ranked higher.

Function Signature

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

Constraints

  • 1 <= nums.length <= 10^5
  • k is always valid (1 <= k <= number of unique elements).
  • Expected Time Complexity: O(n)
  • Expected Space Complexity: O(n)

Examples

Example 1: Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] Explanation: 1 appears 3 times, 2 appears 2 times, and 3 appears 1 time.

Example 2: Input: nums = [4, 4, 2, 2, 3, 3], k = 2 Output: [4, 2] Explanation: 4, 2, and 3 all appear 2 times. Since 4 and 2 appeared before 3 in the input, they are returned first.

Edge Cases

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

Hints

Hint 1

Use a hash map to store the frequency of each number while keeping track of the first occurrence index to handle ties.

Hint 2

Since the maximum possible frequency is the length of the array, consider using a list of lists (buckets) where the index represents the frequency.

Hint 3

Traverse the frequency buckets from highest count to lowest count, collecting elements while maintaining the relative order of first appearances.

Follow-up questions

  • How would you modify your approach if memory was extremely constrained and the frequency distribution was heavily skewed?
  • If the input stream was infinite, how would you maintain the top K most frequent elements in real-time?
  • What would change if the requirement was to return the k *least* frequent elements instead?