Skip to content

013 — Top K Frequent Elements

Source

  • Original source: Classic capstone interview problem (count then heap)
  • Platform: LeetCode — https://leetcode.com/problems/top-k-frequent-elements/
  • Topic: hashing + heaps
  • Difficulty: Medium
  • Pattern: Frequency hashmap, তারপর k-টা সবচেয়ে ঘন element তোলা (heap বা bucket)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 05 hashing (প্রতিটা element কতবার আসে তার count একটা dictionary-তে O(1)-এ রাখা) আর 08 heaps (সেই count-গুলোর উপর size-k heap চালিয়ে সবচেয়ে ঘন k-টা তোলা)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে একটা integer array আর একটা সংখ্যা k দেওয়া। তোমার কাজ: array-তে কোন কোন সংখ্যা সবচেয়ে বেশিবার এসেছে, তার মধ্যে শীর্ষ k-টা সংখ্যা ফেরত দাও। শুধু কোন সংখ্যা ক'বার এসেছে সেটা গুনে, সবচেয়ে ঘন k-টা বেছে নেওয়া — order কোনটা আগে কোনটা পরে, তা সাধারণত গুরুত্বপূর্ণ নয়।

nums = [1, 1, 1, 2, 2, 3], k = 2
গণনা : 1 -> 3 বার, 2 -> 2 বার, 3 -> 1 বার
শীর্ষ 2 ঘন : [1, 2]

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 05 hashing থেকে: প্রতিটা সংখ্যা কতবার এসেছে তা একটা frequency hashmap (Counter/dict)-এ এক পাসে গোনা — O(1)-এ count বাড়ানো ও পড়া।
  • 08 heaps থেকে: সেই (element, count) জোড়াগুলোর উপর একটা size-k min-heap চালিয়ে সবচেয়ে বড় count-ওয়ালা k-টা ধরে রাখা।

একা hashing দেয় "ক'বার এসেছে" দ্রুত গোনা; একা heap দেয় "টপ-k বের করা"। দুটো মিললে O(n log k), পুরো sort ছাড়াই।

3. What is the hidden math or logic?

লুকানো logic দুই ধাপের: প্রথমে একটা frequency map, যা প্রতিটা distinct value-কে তার গণনায় map করে — এটাই raw data-কে "value → count" তথ্যে রূপ দেয়। তারপর সমস্যাটা হয়ে যায় ঠিক একটা top-k order statistic (012-এর মতো), কিন্তু এবার key হিসেবে count। আরেকটা সূক্ষ্ম সত্য: count কখনো len(nums)-এর বেশি হতে পারে না — তাই count-কে index ধরে একটা bucket array-ও বানানো যায়, যা O(n) দেয়।

4. Which data structure is needed?

  • একটা frequency hashmap (collections.Counter, 05 hashing) — গণনার জন্য।
  • শীর্ষ k তুলতে একটা size-k min-heap (heapq, 08 heaps) — count কে priority ধরে।
  • (বিকল্প) count-কে index ধরা একটা bucket list — O(n) সমাধানের জন্য।

5. Why this data structure fits

hashmap-এ count বাড়ানো ও পড়া O(1), তাই n-টা element একবার scan করেই সব গণনা — এটা ছাড়া count করতে nested loop লাগত (O(n^2))। এরপর distinct value সংখ্যা m-এর উপর size-k min-heap চালালে শীর্ষ k পেতে O(m log k), যা পুরো sort (O(m log m))-এর চেয়ে ভালো যখন k ছোট। তাই hashing (05) দেয় দ্রুত গণনা, heap (08) দেয় দ্রুত top-k — এই দুই খাপ মিলেই সমাধান। আর যদি একদম O(n) চাও, count <= n সত্যটা bucket array-কে সম্ভব করে।

6. Real-life analogy

ভাবো তুমি একটা দোকানের সারাদিনের বিক্রি দেখছ — কোন জিনিস ক'টা বিক্রি হলো। প্রথমে তুমি প্রতিটা পণ্যের পাশে একটা ট্যালি মার্ক রাখো (এটা hashmap)। দিনশেষে তুমি শুধু "সবচেয়ে বেশি বিক্রি হওয়া 3টা পণ্য" জানতে চাও — সব পণ্য বিক্রি অনুযায়ী সাজানোর দরকার নেই, শুধু একটা ছোট "টপ-3 তালিকা" রাখলেই হয়, যেখানে সবচেয়ে কম-বিক্রির জনকে দরকারে বাদ দাও। সেই ছোট তালিকাটাই size-k heap।

7. Visual explanation

nums = [1,1,1,2,2,3], k = 2 — আগে count, তারপর size-2 min-heap (count দিয়ে compare):

count : {1: 3, 2: 2, 3: 1}

push (3,1)        heap = [(3,1)]                      # (count, value)
push (2,2)        heap = [(2,2), (3,1)]               size == k
নাও (1,3): 1 > 2(top count)? না -> skip               heap = [(2,2), (3,1)]
                                                       (অর্থাৎ count 1-এর value 3 বাদ)

heap-এ পড়ে আছে count 3 আর 2-ওয়ালা value -> top-2 = [1, 2]

8. Example input and output

Input : nums=[1,1,1,2,2,3], k=2  -> Output: [1, 2]   (order matter করে না)
Input : nums=[1], k=1            -> Output: [1]

Edge case 1 (সব আলাদা): nums=[4,5,6], k=2     -> যেকোনো 2টা, যেমন [4,5]
Edge case 2 (সব একরকম): nums=[7,7,7], k=1     -> [7]
Edge case 3 (k = distinct সংখ্যা): nums=[1,2], k=2 -> [1, 2]

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা distinct value-র জন্য পুরো array ঘুরে গুনি ক'বার আছে, তারপর সব (value, count) জোড়া count দিয়ে sort করি, উপরের k-টা নিই।

counts = {}
for x in nums:
    counts[x] = nums.count(x)        # প্রতিবার পুরো array গোনা!
sorted_pairs = sort(counts by count desc)
return প্রথম k টা value

10. Why brute force is slow

nums.count(x) নিজেই O(n), আর প্রতিটা element-এ ডাকলে O(n^2) গণনা — একই গোনা বারবার। এমনকি count ঠিকভাবে hashmap-এ করলেও, তারপর সব distinct value sort করা O(m log m), যেখানে আমাদের শুধু top-k দরকার। heap (08) সেই sort-কে O(m log k)-এ আর bucket O(m)-এ নামায়। মূল অপচয়: পুরো order বের করা, অথচ লাগে মাত্র k।

11. Key observation

মূল observation: সমস্যাটা দুই অংশ — "ক'বার এসেছে" (গণনা) আর "সবচেয়ে ঘন k-টা" (top-k)। প্রথম অংশ একটা hashmap এক পাসে শেষ করে; দ্বিতীয় অংশটা ঠিক একটা order-statistic problem, যেখানে priority = count। আর একটা বাড়তি সত্য: যেহেতু কোনো count len(nums)-এর বেশি নয়, count-কে সরাসরি bucket index বানিয়ে পুরো sort/heap এড়িয়ে O(n)-এ পৌঁছানো যায়। এই দুই-অংশে ভাঙাটাই চাবি।

12. Optimized intuition

প্রথমে Counter(nums) দিয়ে frequency map বানাও। তারপর একটা size-k min-heap-এ (count, value) জোড়া ঢোকাও — k-এর বেশি হলে সবচেয়ে কম count-ওয়ালা top pop করে দাও। সব distinct value শেষ হলে heap-এ ঠিক সবচেয়ে ঘন k-টা value পড়ে থাকে; তাদের বের করো। (O(n) চাইলে: count-কে index ধরে buckets[count]-এ value জমাও, তারপর বড় count থেকে ছোট দিকে হেঁটে k-টা তুলে নাও।)

13. Thinking tweak

মোচড়: "সব কিছু count দিয়ে sort করে উপরের k নেব" ভাবার বদলে দুই ধাপ আলাদা করো — আগে hashmap-এ গোনো, তারপর top-k-এর জন্য পুরো sort নয়, একটা ছোট size-k heap (বা count-indexed bucket) ব্যবহার করো। গণনা আর নির্বাচন আলাদা করলেই খরচ কমে।

14. Step-by-step dry run

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

  1. Counter বানাও: {1: 3, 2: 2, 3: 1}; heap []
  2. (3, 1) push → heap = [(3,1)]
  3. (2, 2) push → heap = [(2,2),(3,1)] (size 2 = k)
  4. (1, 3): push করে size 3 → pop সবচেয়ে ছোট count (1,3) → heap = [(2,2),(3,1)]
  5. heap-এ value: {1, 2} → return [1, 2]

15. Python solution

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)                 # value -> কতবার (05 hashing)
    heap = []                              # size-k min-heap of (count, value)
    for value, cnt in counts.items():
        heapq.heappush(heap, (cnt, value))
        if len(heap) > k:                  # k-এর বেশি হলে সবচেয়ে কম ঘনটা ফেলো
            heapq.heappop(heap)
    return [value for cnt, value in heap]  # heap-এ পড়ে থাকা k-টাই শীর্ষ

# ---- tests ----
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]
assert sorted(top_k_frequent([7, 7, 7], 1)) == [7]              # সব একরকম
assert sorted(top_k_frequent([1, 2], 2)) == [1, 2]             # k = distinct
assert sorted(top_k_frequent([4, 4, 5, 5, 6], 2)) == [4, 5]   # tie ভেঙে শীর্ষ 2
assert sorted(top_k_frequent([-1, -1, -2], 1)) == [-1]        # negative সহ
print("সব test pass!")

16. Line-by-line code explanation

  • counts = Counter(nums) — এক পাসে প্রতিটা value-র গণনা (05 hashing); O(n)।
  • heap = [] — size-k min-heap, element হবে (count, value) tuple যাতে count দিয়ে compare হয়।
  • for value, cnt in counts.items() — প্রতিটা distinct value একবার দেখি (m-টা)।
  • heapq.heappush(heap, (cnt, value)) — count কে প্রথম ধরে heap-এ ঢোকাই।
  • if len(heap) > k: heapq.heappop(heap) — size k ছাড়ালে সবচেয়ে কম count-ওয়ালা (top) বাদ; ফলে সবসময় শীর্ষ k থাকে।
  • return [value for cnt, value in heap] — heap-এ পড়ে থাকা জোড়াগুলোর value-ই উত্তর।

17. Output walkthrough

[1,1,1,2,2,3], k=2-এ count {1:3, 2:2, 3:1}; heap-এ শেষমেশ (3,1) আর (2,2) টেকে, (1,3) কম count-এ বাদ; value {1,2} → assert (sorted করে) pass। সব-একরকম, k=distinct, tie, negative — সব case ঠিক (order matter করে না বলে test-এ sorted দিয়ে মিলিয়েছি)। শেষে print: সব test pass!।

18. Time complexity

O(n log k) — গণনা O(n); তারপর m-টা distinct value-র উপর size-k heap, O(m log k) ≤ O(n log k)। Bucket পথে পুরোটা O(n)।

19. Space complexity

O(n) — frequency map সবচেয়ে খারাপ ক্ষেত্রে n-টা distinct value রাখে; heap O(k) extra। Bucket পথেও O(n)।

20. Common mistakes

  • heap-এ (value, count) রাখা — তখন value দিয়ে compare হবে, count দিয়ে নয়; tuple-এ count আগে রাখতে হবে।
  • max-heap বানিয়ে k বার pop (O(m log m)) — size-k min-heap-ই আসল সাশ্রয়।
  • count ঠিকভাবে hashmap-এ না করে list.count বারবার ডাকা — O(n^2) ফাঁদ।
  • order জরুরি ধরে নেওয়া — সাধারণত নয়; জরুরি হলে আলাদা করে sort/stable করতে হয়।

21. Which basic problem this inherits from

ভিত্তি: frequency counting hashmap (05 hashing, ../../05-hashing/) + size-k heap দিয়ে top-k order statistic (08 heaps, ../../08-heaps-and-priority-queues/, আর 012-এর heap চিন্তা)। এই দুটো cold জানা থাকলে "count then top-k" নিজে থেকেই আসে।

22. Similar harder problems

23. Pattern learned

Count then top-k (hashmap + size-k heap / bucket): আগে frequency hashmap-এ গোনা, তারপর সেই count-কে priority ধরে size-k heap (বা count-indexed bucket) দিয়ে শীর্ষ k তোলা। "সবচেয়ে ঘন/কম-ঘন k-টা"-জাতীয় problem-এর canonical দুই-ধাপ।

24. Final summary

ভবিষ্যতের আমাকে: "top-k frequent / most common k" শুনলেই দুই ধাপ মনে করবে — (১) Counter দিয়ে গোনো, (২) size-k min-heap-এ (count, value) ঢুকিয়ে top-k তোলো (O(n log k))। tuple-এ count আগে রাখতে ভুলো না। একদম O(n) চাইলে count <= n সত্যটা কাজে লাগিয়ে count-indexed bucket বানাও।

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