Skip to content

006 — Top K Frequent Elements

Source

  • Original source: Classic top-K with frequency counting
  • Platform: LeetCode — https://leetcode.com/problems/top-k-frequent-elements/
  • Topic: heap / priority queue
  • Difficulty: Medium
  • Pattern: Top-K + counting
  • Basic idea inherited from: 05-hashing frequency maps — আগে dict দিয়ে count, তারপর 08 top-K pattern

1. Problem in simple words

একটা সংখ্যার array আর একটা সংখ্যা k দেওয়া আছে। তোমাকে সেই k-টা element বের করতে হবে যারা array-তে সবচেয়ে বেশিবার এসেছে। উত্তরের element-গুলোর order matter করে না — শুধু সঠিক k-টা চাই।

nums = [1, 1, 1, 2, 2, 3],  k = 2  ->  [1, 2]   (1 এসেছে 3 বার, 2 এসেছে 2 বার)

2. Which basic idea does this inherit from?

দুটো ভিত একসাথে। প্রথমে 05-hashing-এর frequency map — একটা dict দিয়ে কে কতবার এসেছে গোনা। তারপর 08-এর top-K pattern — সেই count-গুলোর উপর size-k min-heap চালিয়ে সবচেয়ে বেশিবার আসা k-টা বের করা। অর্থাৎ "count, then top-K"।

3. What is the hidden math or logic?

লুকানো logic দুই ধাপের: (1) প্রতিটা distinct value-র frequency বের করা একটা hashing exercise — O(n)। (2) এরপর প্রশ্নটা দাঁড়ায় "সবচেয়ে বড় k-টা frequency-ওয়ালা কে?" — যা ঠিক top-K problem, frequency-ই এখন key। তাই একই size-k min-heap trick, শুধু compare হয় count দিয়ে।

4. Which data structure is needed?

দুটো structure: একটা hash map (frequency count) আর একটা size-k min-heap যেখানে entry হয় (count, value)। min-heap-এর top-এ থাকে "top-K club-এর সবচেয়ে কম-frequent member"।

5. Why this data structure fits

hash map O(n)-এ frequency দেয়, O(1) lookup। তারপর (count, value)-এর size-k min-heap রাখলে top সবসময় club-এর দুর্বলতম (সবচেয়ে কম count)। প্রতিটা নতুন (count, value) শুধু top-এর সাথে লড়ে — push/pop O(log k)। distinct value সংখ্যা m হলে মোট O(m log k), full sort (O(m log m))-এর চেয়ে সস্তা যখন k ছোট।

6. Real-life analogy

ভাবো একটা music app বছরের শেষে "তোমার top k গান" বানাচ্ছে। প্রথমে সে গুনে রাখে প্রতিটা গান কতবার শুনেছ (frequency map)। তারপর top-k লিস্ট বানাতে একটা ছোট VIP তালিকা রাখে — দরজায় দাঁড়িয়ে সবচেয়ে কম-শোনা গানটা। নতুন কোনো গান যদি তার চেয়ে বেশিবার শোনা হয়, সে ঢোকে, দুর্বলটা বাদ। সেই VIP-দরজার যন্ত্রটাই size-k min-heap।

7. Visual explanation

nums = [1, 1, 1, 2, 2, 3], k = 2। আগে count, তারপর size-2 min-heap of (count, value):

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

entries push order (count, value):  (3,1) (2,2) (1,3)

push (3,1)        -> heap [(3,1)]              (size < k)
push (2,2)        -> heap [(2,2),(3,1)]        (size == k, top = (2,2))
(1,3): 1 > 2? না   -> heap [(2,2),(3,1)]         (rejected)

heap-এ values: {1, 2}  ->  উত্তর [1, 2]

8. Example input and output

Input : nums = [1, 1, 1, 2, 2, 3], k = 2  -> Output: [1, 2]   (order free)
Input : nums = [1], k = 1                  -> Output: [1]
Input : nums = [4, 4, 5, 5, 6], k = 2      -> Output: [4, 5]
Input : nums = [7, 7, 8, 8, 9, 9], k = 3   -> Output: [7, 8, 9]

9. Brute force thinking

প্রথম সরল চিন্তা: frequency map বানিয়ে items-গুলোকে count দিয়ে descending sort করো, তারপর প্রথম k-টা value নাও।

{1:3, 2:2, 3:1} -> sort by count desc -> [(1,3),(2,2),(3,1)] -> প্রথম 2 -> [1,2]

10. Why brute force is slow

distinct value সংখ্যা m হলে count-গুলো sort করা O(m log m), অথচ তোমার শুধু top-k লাগছে — পুরো order না। k যখন m-এর চেয়ে অনেক ছোট, full sort অপচয়। (তবে এই brute force সঠিক উত্তর দেয় — শুধু অপ্রয়োজনীয় বেশি কাজ করে।)

11. Key observation

মূল observation: problem টা আসলে দুটো চেনা টুকরোর জোড়া — frequency counting (hashing) + top-K selection (heap)। একবার count পেয়ে গেলে "top k frequent" আর "top k largest"-এর মধ্যে কোনো পার্থক্য নেই, key শুধু count।

12. Optimized intuition

প্রথমে dict-এ frequency গোনো (O(n))। তারপর distinct (count, value)-গুলোর উপর size-k min-heap চালাও: push করো, size k ছাড়ালে দুর্বলতম (সবচেয়ে কম count) pop করো। শেষে heap-এ থাকা k-টা value-ই উত্তর। মোট O(n + m log k)।

13. Thinking tweak

মোচড়: "top k frequent" শুনে ঘাবড়িও না — দুই টুকরোয় ভাঙো: "আগে কে কতবার?" (dict) তারপর "সবচেয়ে বড় k-টা count কাদের?" (size-k min-heap)। যেকোনো "k most/least frequent" problem এই count-then-top-K ছাঁচে ফেলা যায়।

14. Step-by-step dry run

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

  1. count map: {1: 3, 2: 2, 3: 1}
  2. entries: (3,1), (2,2), (1,3) — (count, value) হিসেবে
  3. push (3,1) → heap {(3,1)} (size 1 < 2)
  4. push (2,2) → heap {(2,2),(3,1)}, top = (2,2)
  5. (1,3): count 1 > top count 2? না → reject
  6. heap = {(2,2),(3,1)} → values {2, 1} → return [1, 2] (order free)

15. Python solution

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)               # O(n): কে কতবার এসেছে
    club = []                          # size-k min-heap of (count, value)
    for value, count in freq.items():
        heapq.heappush(club, (count, value))
        if len(club) > k:              # k ছাড়ালে দুর্বলতম (কম count) বাদ
            heapq.heappop(club)
    return [value for count, value in club]   # বাকি k-টা value

# ---- tests ----
assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert sorted(top_k_frequent([1], 1)) == [1]
assert sorted(top_k_frequent([4, 4, 5, 5, 6], 2)) == [4, 5]
assert sorted(top_k_frequent([7, 7, 8, 8, 9, 9], 3)) == [7, 8, 9]
print("সব test pass!")

16. Line-by-line code explanation

  • freq = Counter(nums) — 05-hashing-এর frequency map; O(n)-এ প্রতিটা value-র count।
  • club = [] — size-k min-heap, entry (count, value); count আগে বলে heap count দিয়ে compare করে।
  • heapq.heappush(club, (count, value)) — প্রতিটা distinct value club-এর দরজায় আসে।
  • if len(club) > k: — size k ছাড়ালে top (সবচেয়ে কম count) pop — দুর্বলতম বাদ।
  • heapq.heappop(club) — সেই দুর্বলতমকে সরায়, club-এ সবসময় top-K।
  • return [value for ...] — heap-এ বাকি k-টা entry থেকে শুধু value-গুলো।

17. Output walkthrough

top_k_frequent([1,1,1,2,2,3],2) section 14-এর dry run মেনে {1,2} দেয় — sorted দিয়ে [1,2], assert pass (order free বলে sorted ব্যবহার করেছি)। [1],1 → [1]। [4,4,5,5,6],2 → 4,5-এর count 2, 6-এর 1 → [4,5]। [7,7,8,8,9,9],3 → তিনটারই count 2, k=3 → সব → [7,8,9]। চারটে assert pass করার পরে print হয়: সব test pass!।

18. Time complexity

O(n + m log k) — count O(n), যেখানে m distinct value সংখ্যা; প্রতিটা distinct entry-তে বড়জোর একটা O(log k) push/pop। k ছোট হলে full sort (O(m log m))-এর চেয়ে সস্তা।

19. Space complexity

O(n) — frequency map সবচেয়ে খারাপ ক্ষেত্রে n-টা distinct key ধরতে পারে; heap শুধু O(k)। তাই dominant term map।

20. Common mistakes

  • (value, count) order-এ heap-এ ঢালা — তখন heap value দিয়ে compare করে, count দিয়ে না; tuple-এ count আগে রাখতে হবে।
  • size guard ভুল করে >= k লেখা — তখন একটা কম element থাকে heap-এ, উত্তর ছোট আসে।
  • count না করে সরাসরি nums-এর উপর top-K চালানো — duplicate আলাদা করে গোনা হয় না, frequency হারিয়ে যায়।

21. Which basic problem this inherits from

ভিত্তি দুটো: 05-hashing-এর frequency map (Counter), আর 08 top-K pattern (patterns.md Pattern 1)। এটা #5 (Kth Largest)-এর সরাসরি সম্প্রসারণ — সেখানে key ছিল value নিজে, এখানে key হলো value-র count।

22. Similar harder problems

23. Pattern learned

Count-then-top-K: "k most/least frequent" দেখলে দুই ধাপে ভাবো — dict দিয়ে frequency, তারপর (count, value)-এর size-k min-heap। key শুধু value থেকে count-এ বদলায়, top-K কঙ্কাল একই থাকে। O(n + m log k), stream-friendly।

24. Final summary

ভবিষ্যতের আমাকে: "top k frequent" = Counter + size-k min-heap of (count, value)। আগে গোনো, তারপর club-এর দরজা পাহারা দাও — দুর্বলতম মানে সবচেয়ে কম count। মনে রেখো, frequency problem-এর অর্ধেক সবসময় একটা hash map, বাকি অর্ধেক একটা চেনা heap pattern।

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