Find Top K Frequent Elements
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 347. Top K Frequent Elements – given an integer array nums, return the k most frequent elements. Initial requirement: return the top 3 elements; follow-up: generalize to arbitrary k.
https://leetcode.com/problems/top-k-frequent-elements/description/
Quick Answer: This question evaluates a candidate's proficiency with frequency counting, selection techniques, use of appropriate data structures, and algorithmic time and space complexity analysis.
Given an integer array nums and an integer k, return a list of the k elements that appear most frequently in nums. Order the result by descending frequency; for elements with equal frequency, order them by ascending numeric value. Assume 1 <= k <= the number of distinct elements in nums.
Constraints
- 1 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= number of distinct elements in nums
- Output length is exactly k
- Order: descending frequency; ties by ascending value
Solution
from typing import List
from collections import Counter
def top_k_frequent(nums: List[int], k: int) -> List[int]:
"""
Return the k elements with highest frequency in nums.
Ordered by descending frequency; ties by ascending numeric value.
"""
freq = Counter(nums)
# Sort by (-frequency, value) to ensure deterministic order
sorted_items = sorted(freq.items(), key=lambda x: (-x[1], x[0]))
return [val for val, count in sorted_items[:k]]
Explanation
We first count frequencies of each value using a hash map. To produce a deterministic result, we sort the distinct values by descending frequency and, when frequencies tie, by ascending numeric value. Finally, we take the first k values from this sorted order.
Time complexity: O(n + u log u), where n is len(nums) and u is the number of distinct elements. Space complexity: O(u).
Hints
- Count occurrences with a hash map (e.g., collections.Counter).
- Sort distinct elements by (-frequency, value) and take the first k.
- Alternatively, use a heap of size k keyed by (frequency, -value) or bucket sort for linear-time selection.