Top k Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Solution

This isn’t too hard to brute force. Sort the array then iterate until you find the first k unique values.

A more efficient way would be using a heap.

  1. Build a HashMap of number -> freq (O(n))
  2. Build a min heap
    • While building, ensure that the size is never > k
    • This felt crazy to me, but it actually works. I need to determine the time complexity of these operations.
  3. Take the top k items from the heap -> freq O(n * log k)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        var m = new HashMap<Integer, Integer>();

        for (var n : nums) {
            m.merge(n, 1, Integer::sum);
        }

        // min pq
        // we want to pin this to k elements, so we want the min to float to the
        // top so that it can be removed
        var pq = new PriorityQueue<Integer>((l, r) -> {
            return Integer.compare(m.get(l), m.get(r));
        });

        // iterate over the map, insert, pin pq size to k
        for (var key : m.keySet()) {
            pq.offer(key);

            if (pq.size() > k) {
                pq.poll();
            }
        }

        // convert the pq to an array
        var out = new int[k];
        for (int i = 0; i < k; i++) {
            out[i] = pq.poll();
        }
        return out;
    }
}

Recent posts from blogs that I like

Reading Visual Art: 183 Sewing for a purpose

Sewing for Garibaldi's redshirts, the flag of a castle, Sir Lancelot, fishermen and sailors, Pentecost costumes, and other purposes.

via The Eclectic Light Company

DeepSeek-R1 and exploring DeepSeek-R1-Distill-Llama-8B

via Simon Willison

FOSDEM '25 protest

Last week, I wrote to object to Jack Dorsey and his company, Block, Inc., being accepted as main track speakers at FOSDEM, and proposed a protest action in response. FOSDEM issued a statement about our plans on Thursday. Today, I have some updates for you regarding the planned action. I would like t...

via Drew DeVault