Problem link ও উৎস
- **Original source:** Classic capstone interview problem (heap of size k vs quickselect)
- **Platform:** LeetCode —
- **Topic:** heaps + sorting/partition
- **Difficulty:** Medium
- **Pattern:** Size-k min-heap (online), অথবা quickselect partition (average O(n))
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **08 heaps** (সবচেয়ে ছোট-এর-মধ্যে-বড় k-টা ধরে রাখতে একটা min-heap) আর **sorting/partition** (quickselect-এ pivot দিয়ে array-কে partition করা, যা quicksort-এর অর্ধেক)। দুই tool জোড়া লাগলেই এই problem-এর দুই রকম সমাধান।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা integer array আর একটা সংখ্যা `k` দেওয়া। তোমার কাজ: array-টা যদি বড় থেকে ছোট সাজাতে, তাহলে `k`-তম স্থানে যে সংখ্যাটা থাকত, সেটা বের করা — মানে **k-তম সবচেয়ে বড়** element। সাবধান: এটা k-তম *আলাদা* (distinct) সংখ্যা নয়, ডুপ্লিকেট গুনে নিয়েই k-তম বড়।
```text
nums = [3, 2, 1, 5, 6, 4], k = 2
বড় থেকে সাজালে : [6, 5, 4, 3, 2, 1]
2nd largest : 5
```
### Input ও output {#8-example-input-and-output}
```text
Input : nums=[3,2,1,5,6,4], k=2 -> Output: 5
Input : nums=[3,2,3,1,2,4,5,5,6], k=4 -> Output: 4 # ডুপ্লিকেট গুনে নিয়ে
Edge case 1 (k = 1, সবচেয়ে বড়): nums=[7,7,7], k=1 -> 7
Edge case 2 (k = n, সবচেয়ে ছোট): nums=[2,1], k=2 -> 1
Edge case 3 (একটা element): nums=[1], k=1 -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা পরীক্ষার শীর্ষ-3 জনকে মনে রাখতে চাও, কিন্তু সব খাতা একসাথে সাজাতে চাও না। তুমি একটা ছোট তিন-জনের "leaderboard" রাখো, যেখানে সবচেয়ে নিচের জন সবার আগে চোখে পড়ে। নতুন খাতা এলে দেখো — এটা কি ওই নিচের জনের চেয়ে ভালো? হলে নিচের জনকে বাদ দিয়ে নতুনকে ঢোকাও। সব খাতা শেষে leaderboard-এর সবচেয়ে নিচের জনই হলো 3rd best। এই "সবচেয়ে দুর্বলটা সবার আগে দেখা যায়" বোর্ডটাই min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **08 heaps** থেকে: একটা **size-k min-heap** ধরা — এতে সবসময় "এ পর্যন্ত দেখা সবচেয়ে বড় k-টা" থাকে, আর heap-এর top (সবচেয়ে ছোট) হলো এই k-টার সবচেয়ে ছোটটা, অর্থাৎ k-তম largest।
- **sorting/partition** থেকে: **quickselect** — quicksort-এর partition step ধার করে, কিন্তু দুই দিকেই recurse না করে শুধু যে দিকে উত্তর আছে সেদিকে যাওয়া।
একা heap দেয় "টপ-k ধরে রাখার" online ক্ষমতা; একা partition দেয় average O(n)-এ একটা order statistic বের করার ক্ষমতা। দুটো জানলে দুই trade-off-ই হাতে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুটো: (১) heap পথে — **size-k min-heap-এর root সবসময় k-তম largest**, কারণ আমরা শুধু সবচেয়ে বড় k-টা রাখি আর তার মধ্যে সবচেয়ে ছোটটা root-এ থাকে। (২) quickselect পথে — partition করার পর pivot তার **চূড়ান্ত sorted জায়গায়** বসে; সেই index দেখে বলে দেওয়া যায় উত্তর pivot-এই, নাকি বাঁ/ডান অংশে। "k-তম largest" = "index `n-k`-তম smallest", এই rank-translation-টাই চাবি।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো রাস্তা:
- **Heap পথ:** Python-এর `heapq` (min-heap), size `k`-তে আটকানো (08 heaps)।
- **Quickselect পথ:** শুধু input **array** নিজেই, in-place partition (sorting/partition) — extra structure লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
min-heap-এ push আর pop দুটোই O(log k), তাই k ছোট হলে (বা data stream-এ এলে) এটা চমৎকার — পুরো array sort না করেই (যা O(n log n)) আমরা O(n log k)-এ top-k পাই, আর root-এ O(1)-এ k-তম largest। অন্যদিকে quickselect partition (03)-কে কাজে লাগিয়ে average O(n)-এ একই উত্তর দেয়, কারণ প্রতিবার অর্ধেক অংশ ফেলে দিই — পুরো sort-এর মতো দুই দিকে নয়। তাই heap (08) দেয় st-friendly online সমাধান, partition (03) দেয় দ্রুততম average সমাধান — দুটোই problem-টায় নিখুঁত খাপ খায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: পুরো array-টা বড় থেকে ছোট sort করো, তারপর `k`-তম element (index `k-1`) তুলে নাও।
```text
sort করো (descending)
return nums[k-1]
# অথবা ascending sort করে return nums[n-k]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
পুরো sort **O(n log n)** — কিন্তু আমরা তো পুরো order চাই না, শুধু একটামাত্র position চাই। তাই অপ্রয়োজনীয় কাজ হচ্ছে: ছোট দিকের সব element-ও নিখুঁত sorted হয়ে যাচ্ছে, যেগুলো লাগবেই না। heap (08) এটাকে O(n log k)-এ আর quickselect (03) average O(n)-এ নামায়, কারণ তারা শুধু দরকারি অংশটুকুই সাজায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"k-তম largest" জানতে পুরো array sorted করার দরকার নেই — শুধু সবচেয়ে বড় k-টা element আর তাদের মধ্যে সবচেয়ে ছোটটা জানলেই হয়।** একটা size-k min-heap ঠিক সেই k-টাই ধরে রাখে আর সবচেয়ে ছোটটা (= উত্তর) root-এ রাখে। আর quickselect-এ partition-এর পর pivot-এর index বলে দেয় উত্তর কোন দিকে — এক দিক পুরো বাদ। এই এক চিন্তাই কাজ কমিয়ে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**Heap পথ:** একটা min-heap-এ প্রথম `k` element ঢোকাও। তারপর বাকি প্রতিটা element-কে heap-এর top (সবচেয়ে ছোট)-এর সাথে তুলনা করো — বড় হলে top pop করে নতুনকে push। শেষে top-ই k-তম largest। **Quickselect পথ:** target index `n-k` (ascending-এ k-তম largest-এর জায়গা)। random pivot দিয়ে partition করো; pivot যদি target-এ বসে — পেলাম; নাহলে যে দিকে target সে দিকেই recurse, অন্য দিক ফেলে দাও।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব সাজিয়ে k-তমটা নেব" ভাবার বদলে ভাবো "আমার তো মাত্র k-টা বড় element দরকার — বাকিদের নিয়ে মাথা ঘামাব কেন?" পুরো sort-এর জায়গায় হয় একটা ছোট k-আকারের bucket (heap) রাখো, নয় partition দিয়ে অর্ধেক করে ফেলে দাও।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [3,2,1,5,6,4]`, `k = 2` — size-2 min-heap গড়ি (heap-এ top = সবচেয়ে ছোট):
```text
push 3 heap = [3]
push 2 heap = [2, 3] size == k
নাও 1: 1 > 2(top)? না -> skip heap = [2, 3]
নাও 5: 5 > 2(top)? হ্যাঁ -> pop 2, push 5 heap = [3, 5]
নাও 6: 6 > 3(top)? হ্যাঁ -> pop 3, push 6 heap = [5, 6]
নাও 4: 4 > 5(top)? না -> skip heap = [5, 6]
top (সবচেয়ে ছোট 2-টার মধ্যে) = 5 -> 2nd largest = 5
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Heap পথ, `nums = [3,2,1,5,6,4]`, `k = 2`:
1. heap-এ প্রথম 2-টা: push 3, push 2 → `heap = [2, 3]` (top 2)
2. `1`: `1 > 2`? না → skip; `heap = [2, 3]`
3. `5`: `5 > 2`? হ্যাঁ → pop 2, push 5; `heap = [3, 5]`
4. `6`: `6 > 3`? হ্যাঁ → pop 3, push 6; `heap = [5, 6]`
5. `4`: `4 > 5`? না → skip; `heap = [5, 6]`
6. শেষ → top = `5` → return 5
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def find_kth_largest(nums, k):
heap = [] # size-k min-heap (08 heaps)
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k: # k-এর বেশি হলে সবচেয়ে ছোটটা ফেলে দাও
heapq.heappop(heap)
return heap[0] # top = k-টা বড়-এর মধ্যে সবচেয়ে ছোট = k-তম largest
# ---- tests ----
assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4 # ডুপ্লিকেট গোনা হয়
assert find_kth_largest([7, 7, 7], 1) == 7 # k = 1, সবচেয়ে বড়
assert find_kth_largest([2, 1], 2) == 1 # k = n, সবচেয়ে ছোট
assert find_kth_largest([1], 1) == 1 # একটা element
assert find_kth_largest([-1, -1, 0], 1) == 0 # negative সহ
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `heap = []` — খালি min-heap; Python-এর `heapq` default-এ min-heap (08 heaps)।
- `for x in nums` — প্রতিটা element একবার দেখি (single pass)।
- `heapq.heappush(heap, x)` — element ঢোকাই, O(log k)।
- `if len(heap) > k: heapq.heappop(heap)` — size k-এর বেশি হলে সবচেয়ে ছোটটা (top) বের করে দাও; ফলে heap-এ সবসময় সবচেয়ে বড় k-টাই থাকে।
- `return heap[0]` — heap-এর top হলো এই k-টার সবচেয়ে ছোট = k-তম largest।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,2,1,5,6,4], k=2`-এ heap গড়তে গড়তে এক সময় `[5,6]` হয় (সবচেয়ে বড় 2-টা), top 5; return 5 — assert pass। ডুপ্লিকেট-ওয়ালা `[3,2,3,1,2,4,5,5,6], k=4`-এ সবচেয়ে বড় 4-টা `{6,5,5,4}`, তার সবচেয়ে ছোট 4 → সঠিক। `k=1`, `k=n`, একটা element, negative — সব case ঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log k)** (heap পথ) — n-টা element, প্রতিটায় O(log k) push/pop। Quickselect পথে average **O(n)**, worst-case O(n^2) (random pivot সেই worst এড়ায়)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** (heap পথ) — heap সর্বোচ্চ k element রাখে। Quickselect in-place হলে O(1) extra (recursion stack বাদে)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- max-heap বানিয়ে n বার pop করা (O(n log n)) — তখন heap-এর সুবিধাই থাকে না; size-k **min**-heap-ই আসল চাল।
- "k-তম largest" আর "k-তম distinct largest" গুলিয়ে ফেলা — এখানে ডুপ্লিকেট গোনা হয়।
- index off-by-one: ascending sort-এ k-তম largest হলো `nums[n-k]`, `nums[k-1]` নয় (descending হলে উল্টো)।
- quickselect-এ fixed pivot (যেমন সবসময় শেষ element) নেওয়া — already-sorted input-এ O(n^2); random pivot নাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: heap operations / size-limited heap (08 heaps, [../../08-heap-priority-queue/](../../08-heap-priority-queue/README.md)) + quicksort-এর partition step থেকে quickselect (sorting, [পূর্বশর্ত](../../02-arrays-and-strings/README.md))। এই দুটো cold জানা থাকলে দুই রকম সমাধানই নিজে থেকে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Smallest Element in a Sorted Matrix (heap বা binary search on value) —