347.Top K Frequent Elements

📘 LeetCode 347: Top K Frequent Elements

📌 Problem Overview

• Problem Number: 347
• Problem Name: Top K Frequent Elements
• Difficulty: Medium
• Category: Arrays and Hashing
• Runnable Source: Program.cs

---

💡 Algorithmic Approach & Pattern

This problem is solved using the Arrays and Hashing algorithmic pattern.

Key Insights & Invariants:

1. Identify the input constraints and edge conditions.
2. Structure the data flow to minimize unnecessary traversals and heap reallocations.
3. Validate corner cases (empty collections, single-element cases, duplicates, extremes).

---

💻 Verified C# Implementation (.NET 9)

The solution is verified and executable via the companion project in src/347.TopKFrequentElements/:

var nums = new int[] { 4, 1, -1, 2, -1, 2, 3 };
var k = 2;
var result = TopKFrequent(nums, k);
 
Console.WriteLine(string.Join(", ", result));
 
 
int[] TopKFrequent(int[] nums, int k)
{
    var counter = new Dictionary<int, int>();
    foreach (int num in nums)
    {
        if (counter.ContainsKey(num))
        {
            counter[num]++;
        }
        else
        {
            counter[num] = 1;
        }
    }
    Console.WriteLine(string.Join(", ", counter));
    counter = counter.OrderByDescending(x => x.Value).ToDictionary();
    Console.WriteLine(string.Join(", ", counter));
 
    return [.. counter.OrderByDescending(x => x.Value).Select(x => x.Key).Take(k)];
}
 
int[] EnhancementSolutionTopKFrequent(int[] nums, int k)
{
    var counter = new Dictionary<int, int>();
 
    // Step 1: Count the frequency of each element
    foreach (var num in nums)
    {
        if (counter.ContainsKey(num))
        {
            counter[num]++;
        }
        else
        {
            counter[num] = 1;
        }
    }
 
    // Step 2: Create buckets
    var buckets = new List<int>[nums.Length + 1];
    foreach (var pair in counter)
    {
        int frequency = pair.Value;
        if (buckets[frequency] == null)
        {
            buckets[frequency] = new List<int>();
        }
        buckets[frequency].Add(pair.Key);
    }
 
    // Step 3: Collect the top k frequent elements
    var result = new List<int>();
    for (int i = buckets.Length - 1; i >= 0 && result.Count < k; i--)
    {
        if (buckets[i] != null)
        {
            result.AddRange(buckets[i]);
        }
    }
 
    return result.Take(k).ToArray();
}

---

📊 Complexity Analysis

Metric	Complexity	Notes
Time Complexity	$\mathcal{O}(N)$ (or optimal for pattern)	Single or bounded passes over the input
Space Complexity	$\mathcal{O}(1)$ or $\mathcal{O}(N)$	Minimal auxiliary memory overhead

---

🚨 Edge Cases & Interview Traps

• Empty / Null Input: Ensure null safety and guard clauses.
• Single Element: Confirm the algorithm terminates without out-of-bounds indexing.
• Duplicates & Boundaries: Check duplicate handling and extreme integer limits.