011 — Top K Frequent Elements¶

Source¶

Original source: Classic frequency + bucket-sort exercise
Platform: LeetCode — https://leetcode.com/problems/top-k-frequent-elements/
Topic: hash map (Counter) + bucket sort
Difficulty: Medium
Pattern: frequency counting
Basic idea inherited from: Counter + bucket idea — গুনে ফেলো, তারপর frequency নিয়ে ভাবো

1. Problem in simple words¶

একটা সংখ্যার array nums আর একটা সংখ্যা k দেওয়া আছে। যে kটা element সবচেয়ে বেশিবার এসেছে, সেগুলো ফেরত দিতে হবে। উত্তরের ক্রম যেকোনো হতে পারে।

nums = [1, 1, 1, 2, 2, 3], k = 2
1 এসেছে 3 বার, 2 এসেছে 2 বার, 3 এসেছে 1 বার
→ সবচেয়ে frequent 2টা: [1, 2]

2. Which basic idea does this inherit from?¶

এটা frequency counting (Pattern 1)-এর সরাসরি সন্তান। আগে শিখেছ এক pass-এ value → count বানাতে। এখানে সেই count বানানোর পর আরেক ধাপ: count অনুযায়ী top-k বের করা। নতুন কৌশল হলো bucket idea — count-কেই index বানিয়ে sort এড়ানো।

3. What is the hidden math or logic?¶

দুই স্তরের logic। প্রথমত, কোনো element কতবার এসেছে সেটা একটা hash map-এ গুনে রাখা যায়। দ্বিতীয়ত — একটা সূক্ষ্ম পর্যবেক্ষণ — n দৈর্ঘ্যের array-তে কোনো frequency কখনো n-এর বেশি হতে পারে না। তাই frequency-গুলো 0..n সীমার মধ্যে; এই সীমিত range-কে কাজে লাগিয়ে comparison-sort (O(n log n)) এড়িয়ে bucket দিয়ে O(n)-এ top-k তোলা যায়।

4. Which data structure is needed?¶

দুটো জিনিস:

একটা Counter (collections.Counter), অর্থাৎ value → frequency hash map।
একটা bucket array, যেখানে buckets[f] ধরে রাখে যেসব value-র frequency ঠিক f। index নিজেই frequency বলে দেয়, তাই আলাদা sort লাগে না।

5. Why this data structure fits¶

Counter এক pass-এ O(n)-এ গোনা শেষ করে। আর frequency যেহেতু 0..n-এ আবদ্ধ, একটা (n+1)-দৈর্ঘ্যের bucket array-তে value-দের frequency ধরে বসিয়ে দিলে বড় frequency থেকে নিচে নামতে নামতে প্রথম kটা তুলে নেওয়া যায় — পুরোটাই O(n)। Heap দিয়েও হয় (O(n log k)), কিন্তু bucket এখানে আরও পরিষ্কার ও দ্রুত।

6. Real-life analogy¶

ভাবো একটা ভোটগণনা: প্রথমে প্রতিটা প্রার্থীর ভোট গুনে ফেললে (Counter)। এবার পুরস্কার দিতে তুমি প্রার্থীদের নাম sort করো না — বরং "যার 100 ভোট সে এই তাকে, যার 99 ওই তাকে" করে ভোটসংখ্যা ধরে তাক সাজাও (bucket)। সবচেয়ে উঁচু তাক থেকে নিচে নামতে নামতে প্রথম k জন বিজয়ী তুলে নাও।

7. Visual explanation¶

nums = [1,1,1,2,2,3], k = 2। প্রথমে Counter, তারপর frequency-কে index ধরে bucket:

Counter:  {1: 3, 2: 2, 3: 1}

bucket index (frequency):  0    1    2    3
                          [ ]  [3]  [2]  [1]

উঁচু থেকে নিচে: freq=3 → 1 নাও (result=[1])
                freq=2 → 2 নাও (result=[1,2]) → len == k, থামো

8. Example input and output¶

Input : nums = [1,1,1,2,2,3], k = 2    Output: [1, 2]   (ক্রম যেকোনো)
Input : nums = [1],           k = 1    Output: [1]
Input : nums = [4,4,4,5,5,6], k = 2    Output: [4, 5]
Input : nums = [1,2,3,4],     k = 4    Output: [1,2,3,4]

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা distinct value-র frequency গোনো, তারপর সব (value, frequency) জোড়াকে frequency অনুযায়ী descending sort করে প্রথম k-টা নাও।

count = প্রতিটা value-র frequency
pairs = count.items() কে frequency অনুযায়ী বড় থেকে ছোট sort
return প্রথম k-টা value

10. Why brute force is slow¶

Sort করা মানে O(n log n) (distinct value সংখ্যার উপর)। অথচ আমাদের পুরো ক্রম দরকার নেই — শুধু উপরের k-টা চাই। আর frequency-গুলো 0..n-এ সীমাবদ্ধ থাকায় comparison-sort পুরোটাই অপ্রয়োজনীয়; সীমিত range মানেই counting/bucket দিয়ে O(n)-এ সারা যায়।

11. Key observation¶

মূল observation: frequency নিজেই একটা ছোট, সীমিত সংখ্যা (0 থেকে n)। তাই frequency-কে array-র index বানিয়ে value-দের সেখানে ফেলে দেওয়া যায়; উঁচু index থেকে নিচে নামলেই descending ক্রম বিনামূল্যে পাওয়া যায় — কোনো comparison sort ছাড়াই।

12. Optimized intuition¶

প্রথমে Counter(nums)। তারপর (n+1)-দৈর্ঘ্যের buckets বানাও; প্রতিটা (value, freq)-কে buckets[freq]-এ রাখো। এবার freq = n থেকে 1 পর্যন্ত নিচে নামো, প্রতিটা bucket-এর value-গুলো নিতে থাকো, ঠিক kটা হলে থামো। পুরোটা O(n) time।

13. Thinking tweak¶

মোচড়: raw item নিয়ে ভেবো না — count নিয়ে ভাবো, আর count যদি সীমিত range-এ থাকে তবে sort না করে index বানাও। এই দ্বিতীয় অংশটাই Pattern 1-কে এক ধাপ এগিয়ে নেয়: counting + bucket = O(n) selection।

14. Step-by-step dry run¶

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

count = {1: 3, 2: 2, 3: 1}।
buckets: index 3 → [1], index 2 → [2], index 1 → [3], বাকি খালি।
freq = 6..4: সব খালি, কিছু নেওয়া হলো না।
freq = 3: 1 নাও → result = [1]।
freq = 2: 2 নাও → result = [1, 2] → len == k, return [1, 2]।

15. Python solution¶

from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)                        # value -> frequency
    buckets = [[] for _ in range(len(nums) + 1)] # index = frequency
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):  # বেশি frequency আগে
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

# ---- tests ----
assert set(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == {1, 2}
assert top_k_frequent([1], 1) == [1]
assert set(top_k_frequent([4, 4, 4, 5, 5, 6], 2)) == {4, 5}
assert set(top_k_frequent([1, 2, 3, 4], 4)) == {1, 2, 3, 4}
print("সব test pass!")

16. Line-by-line code explanation¶

count = Counter(nums) — এক pass-এ প্রতিটা value-র frequency।
buckets = [[] for _ in range(len(nums) + 1)] — index 0..n; index মানেই frequency।
for num, freq in count.items(): buckets[freq].append(num) — প্রতিটা value তার frequency-bucket-এ।
for freq in range(len(buckets) - 1, 0, -1) — সবচেয়ে বড় frequency থেকে নিচে নামি।
result.append(num) ও if len(result) == k: return result — k-টা হয়ে গেলেই থামি।
test-এ set(...) দিয়ে মেলাই, কারণ সমান-frequency element-দের ক্রম যেকোনো হতে পারে।

17. Output walkthrough¶

[1,1,1,2,2,3]-এ Counter {1:3, 2:2, 3:1}; bucket[3]=[1], bucket[2]=[2], bucket[1]=[3]। উঁচু থেকে নিচে নেমে 1 তারপর 2 নিয়ে k=2 পূর্ণ → {1,2}। [1,2,3,4] k=4-এ সবার frequency 1, bucket[1]=[1,2,3,4]; সব নিয়ে {1,2,3,4}। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — Counting O(n), bucket ভরা O(distinct) ≤ O(n), bucket থেকে তোলা মোট O(n)। Comparison-sort এড়িয়ে linear।

19. Space complexity¶

O(n) — Counter আর bucket array দুটোই worst case-এ O(n) জায়গা নেয়।

20. Common mistakes¶

bucket array n+1 দৈর্ঘ্যের না বানিয়ে n বানানো — frequency ঠিক n হতে পারে (সব element সমান), তখন index out of range।
সমান-frequency element-দের নির্দিষ্ট ক্রম ধরে নেওয়া — problem যেকোনো ক্রম মানে; assert-এ set ব্যবহার নিরাপদ।
range(...) ভুল দিকে চালানো — descending (len-1 থেকে 0-র দিকে, step -1) না হলে কম-frequent element আগে চলে আসবে।

21. Which basic problem this inherits from¶

ভিত্তি: frequency counting (Pattern 1) আর Valid Anagram/Ransom Note-এর Counter-অভ্যাস। নতুন সংযোজন bucket sort — সীমিত-range count-কে index বানিয়ে O(n) selection। সম্পূর্ণ চাল ../patterns.md-র Pattern 1-এ।

22. Similar harder problems¶

Sort Characters By Frequency — https://leetcode.com/problems/sort-characters-by-frequency/ (একই bucket idea, string-এ)
Top K Frequent Words — https://leetcode.com/problems/top-k-frequent-words/ (tie ভাঙতে lexicographic order)
Kth Largest Element in an Array — https://leetcode.com/problems/kth-largest-element-in-an-array/ (selection-এর আরেক রূপ)

23. Pattern learned¶

Frequency counting + bucket: আগে value → count গোনো, তারপর count যদি সীমিত range-এ থাকে, তাকে index বানিয়ে sort এড়িয়ে O(n)-এ top-k তুলে নাও।

24. Final summary¶

ভবিষ্যতের আমাকে: "most frequent", "top k" শুনলেই দুই ধাপ মনে পড়বে — Counter দিয়ে গোনো, তারপর "frequency কি সীমিত range-এ?" জিজ্ঞেস করো। হলে bucket; না হলে heap (O(n log k))। মূল শিক্ষা: সীমিত range = sort এড়ানোর সুযোগ।

25. JavaScript solution (with test cases)¶

Map-এ count, তারপর frequency-কে index ধরে bucket — sort এড়িয়ে O(n)।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const sameSet = (a, b) =>
  JSON.stringify([...a].sort((x, y) => x - y)) === JSON.stringify([...b].sort((x, y) => x - y));
// k most frequent elements (count + bucket sort)
function topKFrequent(nums, k) {
  const count = new Map();                         // value -> frequency
  for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []); // index = frequency
  for (const [num, freq] of count) buckets[freq].push(num);
  const result = [];
  for (let freq = buckets.length - 1; freq > 0; freq--) {   // বেশি frequency আগে
    for (const num of buckets[freq]) {
      result.push(num);
      if (result.length === k) return result;
    }
  }
  return result;
}
// ---- test cases (example + edge); সমান-frequency-তে ক্রম যেকোনো, তাই set-compare ----
assert(sameSet(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2]), "classic");
assert(sameSet(topKFrequent([1], 1), [1]), "single");
assert(sameSet(topKFrequent([4, 4, 4, 5, 5, 6], 2), [4, 5]), "two");
assert(sameSet(topKFrequent([1, 2, 3, 4], 4), [1, 2, 3, 4]), "all-tie");   // edge
console.log("সব JS test pass!");

JS টীকা: bucket array Array.from({length: n+1}, () => []) দিয়ে বানাও — new Array(n).fill([]) দিলে সব একই array reference share করত (bug)। সমান-frequency element-দের ক্রম arbitrary, তাই assert-এ set-compare।

26. TypeScript solution (with test cases)¶

function topKFrequent(nums: number[], k: number): number[] {
  const count = new Map<number, number>();         // value -> frequency
  for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of count) buckets[freq].push(num);
  const result: number[] = [];
  for (let freq = buckets.length - 1; freq > 0; freq--) {
    for (const num of buckets[freq]) {
      result.push(num);
      if (result.length === k) return result;
    }
  }
  return result;
}
function expectSet(actual: number[], exp: number[], msg = ""): void {
  const a = [...actual].sort((x, y) => x - y);
  const b = [...exp].sort((x, y) => x - y);
  if (JSON.stringify(a) !== JSON.stringify(b)) throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectSet(topKFrequent([1, 1, 1, 2, 2, 3], 2), [1, 2], "classic");
expectSet(topKFrequent([1, 2, 3, 4], 4), [1, 2, 3, 4], "all-tie");
console.log("সব TS test pass!");

TS টীকা: buckets: number[][] declare করায় nested array-র element type পাকা; Map<number, number> count-এর key/value নিশ্চিত করে — freq সবসময় valid index।

27. কোথায় কাজে লাগে (real-world use)¶

Trending/top-N: সবচেয়ে বেশি দেখা product, hashtag, search query বের করা (top-K by frequency)।
Log/error aggregation: সবচেয়ে ঘন ঘন আসা error code বা endpoint চিহ্নিত করা।
NLP: document-এ সবচেয়ে frequent word/term বের করে keyword extraction।
Cache eviction insight: সবচেয়ে বেশি accessed key খুঁজে hot-set নির্ধারণ।
Recommendation: জনপ্রিয়তম item দ্রুত surface করা।
Analytics dashboard: top-K category/event count দেখানো।

মূল pattern: আগে গোনো, তারপর "frequency কি সীমিত range-এ?" — হলে bucket (sort এড়িয়ে O(n)), নাহলে heap।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।