Top K Frequent Elements

LeetCode 347 | Difficulty: Medium

Medium

Problem Description

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]

Example 3:

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

Output: [1,2]

Constraints:

- `1 <= nums.length <= 10^5`

- `-10^4 <= nums[i] <= 10^4`

- `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.

Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 144 ms)

Metric	Value
Runtime	144 ms
Memory	44.3 MB
Date	2021-11-24

Solution

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
    List<int> result = new List<int>();
    int max = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        if(freq.ContainsKey(nums[i]))
        {
            freq[nums[i]]++;        
            
        }
        else
        {
            freq.Add(nums[i], 1);
        }
        max = Math.Max(freq[nums[i]], max);
    }
    
    Dictionary<int, List<int>> buckets = new Dictionary<int, List<int>>(max+1);
    for (int i = 1; i <= max; i++)
    {
        buckets[i] = new List<int>();
    }
    foreach (var item in freq)
    {
        buckets[item.Value].Add(item.Key);

    }
    
    int last = max;
    while(k>0 && last > 0)
    {
        int current = 0;
        if(buckets[last].Count > 0)
        {
            current = Math.Min(k, buckets[last].Count);
            for (int i = 0; i < current; i++)
            {
                result.Add(buckets[last][i]);
            }
        }
        
        last--;
        k -= current;
    }
    return result.ToArray();
    }
}

📜 1 more C# submission(s)

Submission (2018-04-09) — 308 ms, N/A

public class Solution {
    public IList<int> TopKFrequent(int[] nums, int k) {
        Dictionary<int, int> occurences = new Dictionary<int, int>();
    int m = nums.Length;

    for (int i = 0; i < m; i++)
    {
        if (!occurences.ContainsKey(nums[i]))
        {
            occurences.Add(nums[i], 1);
        }
        else
        {
            occurences[nums[i]]++;
        }
    }
    List<int> result = new List<int>();
    int counter=k;
    foreach (var occurence in occurences.OrderByDescending(x => x.Value))
    {
        if(counter>0) result.Add(occurence.Key);
        counter--;
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.