Medium java coding

How do you return the k most frequent numbers, with the larger number first on a tie?

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, using merge(x, 1, Integer::sum).
  • PriorityQueue holds the top k. Its Javadoc gives O(log n) for offer and poll and O(1) for peek, 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 TreeMap keyed by frequency also works, but it's more code than the heap and no faster.
Sources (3)
  1. LeetCode 347: Top K Frequent Elementsleetcode.com
  2. PriorityQueue Javadoc (Java 21)docs.oracle.com
  3. HashMap.merge Javadoc (Java 21)docs.oracle.com