Find Top K Frequent Elements

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/

Find Top K Frequent Elements

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

Examples

Example 1

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

Explanation: Frequencies: 1->3, 2->2, 3->1. Top 2 are [1,2] in that order.

Example 2

Input: nums = [4,4,1,2,2,3], k = 2
Output: [2,4]

Explanation: Frequencies: 2->2, 4->2, 1->1, 3->1. Tie at frequency 2 is broken by ascending value, so [2,4].

Hints

1. Count occurrences with a hash map (e.g., collections.Counter).
2. Sort distinct elements by (-frequency, value) and take the first k.
3. Alternatively, use a heap of size k keyed by (frequency, -value) or bucket sort for linear-time selection.

Approach

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)