The 30 second answer
First I count with a HashMap from number to frequency. Then I keep a min-heap of size k, ordered by frequency, and on a tie by the smaller number, so the root is always the weakest of the current top k. For each entry I add it, and if the heap grows past k I remove the root. Finally I pop the heap into the result from the back. That's O(n log k) time and O(n) space.
The base problem is LeetCode 347, Top K Frequent Elements. The twist here is the tie rule: when two numbers have the same frequency, the larger number ranks higher. The question also asks which collections you'd use, so name them and say why.
Collections.
HashMap<Integer, Integer>counts in one pass, usingmerge(x, 1, Integer::sum).PriorityQueueholds the top k. Its Javadoc gives O(log n) forofferandpolland O(1) forpeek, so a heap capped at k costs O(log k) per entry.
The comparator is the whole trick. I want to throw out the weakest candidate, so the heap is a min-heap by rank. Lower frequency is weaker. On equal frequency the smaller number is weaker, because the larger one must win. I store int[] {value, count} pairs so there are no wrapper entry objects to sort.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class TopKFrequent {
// Most frequent first; on equal frequency the larger number comes first.
static int[] topK(int[] nums, int k) {
Map<Integer, Integer> counts = new HashMap<>();
for (int x : nums) counts.merge(x, 1, Integer::sum);
// Min-heap of {value, count}: the root is the "worst" of the current top k
// (lowest count, and on a tie the smaller value).
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->
a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
heap.offer(new int[] {e.getKey(), e.getValue()});
if (heap.size() > k) heap.poll(); // drop the worst
}
int[] result = new int[heap.size()];
for (int i = result.length - 1; i >= 0; i--) result[i] = heap.poll()[0];
return result;
}
}topK(new int[] {1, 1, 1, 2, 2, 3}, 2); // [1, 2]
topK(new int[] {4, 4, 7, 7, 2, 2, 9}, 2); // [7, 4] three-way tie: the larger numbers win
topK(new int[] {5, 3, 5, 3, 8}, 3); // [5, 3, 8]Complexity. Counting is O(n). The heap step is O(m log k) for m distinct numbers. The total is O(n log k) time and O(n) space.
Alternatives worth naming.
- Sort all m entries with the same comparator, reversed, and take the first k. That's O(m log m), simpler to write and fine when m is small.
- Bucket sort by frequency gives O(n) time, because a frequency is never larger than n. Inside each bucket you still need to sort by value to honor the tie rule.
- A
TreeMapkeyed by frequency also works, but it's more code than the heap and no faster.
Sources (3)
- LeetCode 347: Top K Frequent Elementsleetcode.com
- PriorityQueue Javadoc (Java 21)docs.oracle.com
- HashMap.merge Javadoc (Java 21)docs.oracle.com