Problem link ও উৎস
- **Original source:** Classic top-K with frequency counting
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Top-K + counting
- **Basic idea inherited from:** `05-hashing` frequency maps — আগে dict দিয়ে count, তারপর `08` top-K pattern
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যার array আর একটা সংখ্যা `k` দেওয়া আছে। তোমাকে সেই `k`-টা element বের করতে হবে যারা array-তে **সবচেয়ে বেশিবার** এসেছে। উত্তরের element-গুলোর order matter করে না — শুধু সঠিক k-টা চাই।
```text
nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] (1 এসেছে 3 বার, 2 এসেছে 2 বার)
```
### Input ও output {#8-example-input-and-output}
```text
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]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা music app বছরের শেষে "তোমার top k গান" বানাচ্ছে। প্রথমে সে গুনে রাখে প্রতিটা গান কতবার শুনেছ (frequency map)। তারপর top-k লিস্ট বানাতে একটা ছোট VIP তালিকা রাখে — দরজায় দাঁড়িয়ে সবচেয়ে কম-শোনা গানটা। নতুন কোনো গান যদি তার চেয়ে বেশিবার শোনা হয়, সে ঢোকে, দুর্বলটা বাদ। সেই VIP-দরজার যন্ত্রটাই size-k min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 ছোট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: frequency map বানিয়ে items-গুলোকে count দিয়ে descending sort করো, তারপর প্রথম k-টা value নাও।
```text
{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 ছাঁচে ফেলা যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 1, 1, 2, 2, 3]`, `k = 2`। আগে count, তারপর size-2 min-heap of `(count, value)`:
```text
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]
```
### ছোট input-এ ধাপে ধাপে {#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)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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-গুলো।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 হারিয়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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}
- Sort Characters By Frequency —