Problem link ও উৎস
- **Original source:** Classic top-K streaming exercise
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Easy
- **Pattern:** Top-K (size-k min-heap)
- **Basic idea inherited from:** `08` top-K pattern — min-heap guards the door
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা class বানাও যেটা একটা চলমান stream-এ সবসময় **k-তম largest** সংখ্যাটা বলতে পারে। Constructor-এ পাবে `k` আর শুরুর কিছু সংখ্যা। তারপর বারবার `add(val)` ডাকা হবে — প্রতিবার নতুন সংখ্যা যোগ হওয়ার **পরে** এ পর্যন্ত দেখা সব সংখ্যার মধ্যে k-তম largest টা return করতে হবে। মনে রেখো, "k-তম largest" মানে duplicate ধরে গোনা — distinct না।
```text
k = 3, শুরু = [4, 5, 8, 2]
add(3) -> 4 add(5) -> 5 add(10) -> 5 add(9) -> 8 add(4) -> 8
```
### Input ও output {#8-example-input-and-output}
```text
KthLargest(3, [4, 5, 8, 2])
add(3) -> 4
add(5) -> 5
add(10) -> 5
add(9) -> 8
add(4) -> 8
Edge: KthLargest(1, []) ; add(-3) -> -3 ; add(-2) -> -2 (k = 1 মানে চলমান max)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা exclusive club-এর দরজায় bouncer ভাবো, ভেতরে ঠিক k-টা সিট। সবচেয়ে দুর্বল member দরজার সবচেয়ে কাছে দাঁড়িয়ে। নতুন কেউ এলে bouncer শুধু তাকে **দরজার ওই দুর্বলতম**-এর সাথে মাপে — সবার সাথে না। নতুন লোক বড় হলে দুর্বলতম বেরিয়ে যায়, নতুন লোক ঢোকে। দরজায় দাঁড়ানো লোকটাই তোমার k-তম largest।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো `08`-এর **top-K pattern**: k largest খুঁজতে একটা **size-k min-heap** রাখো। heap-এর top (সবচেয়ে দুর্বল member) হলো ঠিক k-তম largest — কারণ heap-এ আছে exactly k-টা সবচেয়ে বড় সংখ্যা, আর তাদের মধ্যে সবচেয়ে ছোটটাই top।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **invariant**: প্রতিটা `add`-এর পরে heap-এ ঠিক k-টা element থাকে, আর সেগুলোই এ পর্যন্ত দেখা সংখ্যাগুলোর top-k largest। এই invariant সত্য থাকলে `heap[0]` সবসময় k-তম largest। নতুন সংখ্যা এলে শুধু এতটুকু ঠিক করতে হয় — সে কি club-এ ঢোকার যোগ্য? ঢুকলে সবচেয়ে দুর্বলকে বের করে দাও।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap যার size বড়জোর k** (Python `heapq`)। size-টা কখনো k ছাড়াতে দিই না — ছাড়ালেই top pop।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
stream চলতেই থাকে, তাই একবার sort করে রাখা যায় না — নতুন data বারবার আসে। min-heap-এর top O(1)-এ k-তম largest দেয়, আর প্রতিটা insert O(log k)। শুধু k-টা element রাখায় memory O(k), এমনকি stream অসীম হলেও। পুরো history জমানোর দরকারই নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সংখ্যা একটা list-এ জমাও। `add`-এর সময় পুরো list `sort` করে নিচ থেকে k-তম বড়টা (`sorted_list[-k]`) ফেরত দাও।
```text
add(3): list = [4,5,8,2,3] -> sort -> [2,3,4,5,8] -> [-3] index = 4
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা `add`-এ একটা full `sort` মানে O(n log n), আর `add` হতে পারে অনেকবার — m-টা add-এ মোট **O(m·n log n)**। আমরা পুরো order ব্যবহারই করি না, শুধু k-তম largest লাগে। আর পুরো history জমালে memory O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: k-তম largest-এর জন্য তোমার শুধু **top-k largest সংখ্যাগুলো** জানলেই চলে, বাকিগুলো একদম অপ্রাসঙ্গিক। আর সেই top-k-এর মধ্যে সবচেয়ে ছোটটাই উত্তর — ঠিক একটা size-k min-heap-এর top।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা min-heap-এ শুরুর সংখ্যাগুলো ঢালো, size k-তে নামিয়ে আনো। প্রতিটা `add`-এ নতুন value push করো; size k ছাড়ালে top pop করো (দুর্বলতম বাদ)। তারপর `heap[0]` ফেরত দাও। প্রতিটা `add` O(log k)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "largest খুঁজছি, তাহলে max-heap লাগবে" — এই সহজ ফাঁদে পোড়ো না। k-তম *largest*-এর জন্য একটা *min*-heap লাগে, কারণ একটাই প্রশ্ন matter করে: "তুমি কি আমাদের worst member-এর চেয়ে ভালো?" worst member = min-heap-এর top। জোরে বলো: **"min-heap guards the door."**
### ছবিতে বোঝা {#7-visual-explanation}
`k = 3`, শুরু `[4, 5, 8, 2]` → size-3 min-heap রাখি (top = k-তম largest):
```text
শুরু: সব ঢেলে দিয়ে top-3 রাখি -> heap {4, 5, 8} (top = 4)
add(3): 3 > 4? না -> ঢোকে না heap {4, 5, 8} k-তম = 4
add(5): 5 > 4? হ্যাঁ -> 4 বার, 5 ঢোকে heap {5, 5, 8} k-তম = 5
add(10): 10 > 5? হ্যাঁ -> 5 বার, 10 ঢোকে heap {5, 8, 10} k-তম = 5
add(9): 9 > 5? হ্যাঁ -> 5 বার, 9 ঢোকে heap {8, 9, 10} k-তম = 8
add(4): 4 > 8? না -> ঢোকে না heap {8, 9, 10} k-তম = 8
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`KthLargest(3, [4, 5, 8, 2])`:
1. push 4,5,8,2 → size 4 > 3 → pop top (2) → heap {4,5,8}, top = 4
2. `add(3)`: push 3 → size 4 → pop min (3) → heap {4,5,8}, return 4
3. `add(5)`: push 5 → size 4 → pop min (4) → heap {5,5,8}, return 5
4. `add(10)`: push 10 → size 4 → pop min (5) → heap {5,8,10}, return 5
5. `add(9)`: push 9 → size 4 → pop min (5) → heap {8,9,10}, return 8
6. `add(4)`: push 4 → size 4 → pop min (4) → heap {8,9,10}, return 8
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = nums[:] # input copy করি
heapq.heapify(self.heap) # min-heap বানাও
while len(self.heap) > k: # size-কে k-তে নামাও
heapq.heappop(self.heap) # দুর্বলতম বাদ
def add(self, val):
heapq.heappush(self.heap, val) # নতুন জন দরজায়
if len(self.heap) > self.k: # club ভরে গেলে
heapq.heappop(self.heap) # দুর্বলতম বের করে দাও
return self.heap[0] # top = k-তম largest
# ---- tests ----
kth = KthLargest(3, [4, 5, 8, 2])
assert kth.add(3) == 4
assert kth.add(5) == 5
assert kth.add(10) == 5
assert kth.add(9) == 8
assert kth.add(4) == 8
solo = KthLargest(1, []) # k = 1 -> চলমান max
assert solo.add(-3) == -3
assert solo.add(-2) == -2
assert solo.add(-4) == -2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.heap = nums[:]` — input-এর copy, যাতে caller-এর list-এ হাত না পড়ে।
- `heapq.heapify(self.heap)` — O(n)-এ min-heap বানায়।
- `while len(self.heap) > k:` — শুরুতেই size-কে ঠিক k-তে আনে, ছোট ছোট element pop করে।
- `heapq.heappush(self.heap, val)` — নতুন সংখ্যা ঢোকাও (এখন size হতে পারে k+1)।
- `if len(self.heap) > self.k:` — ছাড়িয়ে গেলে top (দুর্বলতম) pop, size আবার k।
- `return self.heap[0]` — invariant অনুযায়ী top-এই k-তম largest।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
Constructor `[4,5,8,2]`-কে {4,5,8}-এ নামায়, top = 4। তারপর প্রতিটা `add` section 14-র মতো চলে: 4, 5, 5, 8, 8 — পাঁচটা assert pass। `KthLargest(1, [])` চলমান maximum হিসেবে কাজ করে (k=1): −3, −2, তারপর −4 যোগেও top থাকে −2 — তিনটে assert pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
Constructor **O(n log n)** worst case (size নামাতে pop)। প্রতিটা `add` **O(log k)** — একটা push আর বড়জোর একটা pop, heap-এ সবসময় ≤ k element।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — heap-এ সর্বোচ্চ k+1 (তাৎক্ষণিকভাবে), তারপরই k-তে নেমে আসে। পুরো stream জমাতে হয় না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- max-heap ব্যবহার করা — তখন top দেয় 1st largest, k-তম না।
- `add`-এ pop করতে ভুলে গিয়ে heap-কে k ছাড়িয়ে যেতে দেওয়া — তখন `heap[0]` আর k-তম largest থাকে না।
- distinct ভেবে duplicate বাদ দেওয়া — এখানে duplicate গুনতে হয় ([5,5] দুটো আলাদা)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর top-K pattern (`patterns.md` Pattern 1 — "min-heap guards the door")। একই engine #5 (Kth Largest in an Array) আর #7 (K Closest Points)-এও চলে; পার্থক্য শুধু এটা stream-এ, তাই heap-টা object-এর ভেতরে বেঁচে থাকে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Largest Element in an Array —