Problem link ও উৎস
- **Original source:** Classic capstone interview problem (count then heap)
- **Platform:** LeetCode —
- **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।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা integer array আর একটা সংখ্যা `k` দেওয়া। তোমার কাজ: array-তে কোন কোন সংখ্যা সবচেয়ে **বেশিবার** এসেছে, তার মধ্যে শীর্ষ `k`-টা সংখ্যা ফেরত দাও। শুধু কোন সংখ্যা ক'বার এসেছে সেটা গুনে, সবচেয়ে ঘন k-টা বেছে নেওয়া — order কোনটা আগে কোনটা পরে, তা সাধারণত গুরুত্বপূর্ণ নয়।
```text
nums = [1, 1, 1, 2, 2, 3], k = 2
গণনা : 1 -> 3 বার, 2 -> 2 বার, 3 -> 1 বার
শীর্ষ 2 ঘন : [1, 2]
```
### Input ও output {#8-example-input-and-output}
```text
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]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা দোকানের সারাদিনের বিক্রি দেখছ — কোন জিনিস ক'টা বিক্রি হলো। প্রথমে তুমি প্রতিটা পণ্যের পাশে একটা ট্যালি মার্ক রাখো (এটা hashmap)। দিনশেষে তুমি শুধু "সবচেয়ে বেশি বিক্রি হওয়া 3টা পণ্য" জানতে চাও — সব পণ্য বিক্রি অনুযায়ী সাজানোর দরকার নেই, শুধু একটা ছোট "টপ-3 তালিকা" রাখলেই হয়, যেখানে সবচেয়ে কম-বিক্রির জনকে দরকারে বাদ দাও। সেই ছোট তালিকাটাই size-k heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-কে সম্ভব করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা distinct value-র জন্য পুরো array ঘুরে গুনি ক'বার আছে, তারপর সব (value, count) জোড়া count দিয়ে sort করি, উপরের k-টা নিই।
```text
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) ব্যবহার করো। গণনা আর নির্বাচন আলাদা করলেই খরচ কমে।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1,1,1,2,2,3]`, `k = 2` — আগে count, তারপর size-2 min-heap (count দিয়ে compare):
```text
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]
```
### ছোট input-এ ধাপে ধাপে {#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]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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-ই উত্তর।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 করতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: frequency counting hashmap (05 hashing, [../../05-hashing/](../../05-hashing/README.md)) + size-k heap দিয়ে top-k order statistic (08 heaps, [../../08-heap-priority-queue/](../../08-heap-priority-queue/README.md), আর 012-এর heap চিন্তা)। এই দুটো cold জানা থাকলে "count then top-k" নিজে থেকেই আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Largest Element in an Array (একই size-k heap, count ছাড়া) —