Problem link ও উৎস
- **Original source:** Classic heap / sorting warm-up
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Easy
- **Pattern:** Heap / sorting warm-up
- **Basic idea inherited from:** `02-arrays-and-strings` sorting — value-কে original index মনে রেখে order বের করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো athlete-এর score দেওয়া আছে, সব আলাদা। সবচেয়ে বেশি score পায় `"Gold Medal"`, তার পরেরটা `"Silver Medal"`, তার পরেরটা `"Bronze Medal"`। বাকি সবাই তাদের rank-এর সংখ্যাটাই string হিসেবে পায় — চতুর্থ হলে `"4"`, পঞ্চম হলে `"5"`, এভাবে। শেষে **প্রতিটা athlete-এর rank তার নিজের original জায়গায়** ফেরত দিতে হবে, একটা list of string-এ।
```text
score = [5, 4, 3, 2, 1] -> ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
```
### Input ও output {#8-example-input-and-output}
```text
Input : score = [5, 4, 3, 2, 1] -> Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Input : score = [10, 3, 8, 9, 4] -> Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Input : score = [1] -> Output: ["Gold Medal"]
Input : score = [2, 1] -> Output: ["Gold Medal","Silver Medal"]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
Sports day-র শেষে judge স্কোরশিট হাতে নিয়ে বসেছেন। তিনি বারবার "এখন সবচেয়ে বেশি কে?" জিজ্ঞেস করে একজন করে ডেকে medal বা position number দিচ্ছেন — Gold, Silver, Bronze, তারপর 4, 5, 6… প্রতিটা athlete-এর নাম (এখানে original index) তিনি মনে রাখছেন, যাতে result শিটে ঠিক জায়গায় বসাতে পারেন। সেই "বারবার সবচেয়ে বড় দাও" যন্ত্রটাই heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো **sorting, কিন্তু index মনে রেখে**। তোমাকে শুধু সাজালেই হবে না — সাজানোর পরে প্রতিটা score আবার তার আসল জায়গায় বসাতে হবে। তাই value-র সাথে তার original index-টা একসাথে নিয়ে চলা — এটা `02-arrays-and-strings`-এর "sort by key, remember where it came from" move।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic খুব সরল: **descending order-এ position-ই হলো rank**। সবচেয়ে বড় score = rank 1, পরেরটা = rank 2, ইত্যাদি। প্রথম তিনটা rank-এর জন্য আলাদা নাম, বাকিগুলোর জন্য সংখ্যাটাই। তাই কাজটা দাঁড়ায়: প্রতিটা score বড় থেকে ছোট দিকে কত নম্বরে আছে সেটা বের করা, আর সেই অনুযায়ী label বসানো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **max-heap** (বা সমতুল্যভাবে একটা sort)। আমরা `(score, index)` জোড়াগুলো max-heap-এ রাখব, যাতে বারবার pop করলেই বড় থেকে ছোট order-এ score বেরিয়ে আসে — আর সাথে আসা index বলে দেয় answer কোথায় বসাতে হবে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Heap-এর top সবসময় বর্তমান সবচেয়ে বড় score। বারবার pop করলে rank 1, 2, 3, … order-এই পাও — ঠিক যে order-এ label বসাতে হবে। প্রতিটা pop O(log n), আর সাথে আসা index মানে result array-তে সরাসরি লেখা যায়, আলাদা lookup লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা score-এর জন্য পুরো array scan করে দেখো তার চেয়ে বড় কতগুলো আছে — সেই count + 1 হলো তার rank। তারপর rank অনুযায়ী label বসাও।
```text
score = [10, 3, 8, 9, 4]
score[1]=3 -> তার চেয়ে বড়: 10,8,9,4 -> 4টা -> rank 5 -> "5"
```
প্রতিটা element-এর জন্য আরেকবার পুরো array দেখা।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা element-এর rank বের করতে পুরো array scan মানে O(n) প্রতিজনের জন্য, মোট **O(n²)**। অথচ একবার সাজিয়ে নিলেই সব rank একসাথে বেরিয়ে আসে — প্রতিবার আলাদা করে গুনে দেখা নিখাদ অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: rank মানে শুধুই **descending order-এ position**। তাই একটাই sort (বা heap pop sequence) সব rank একসাথে দিয়ে দেয়। আলাদা করে প্রতিজনের জন্য গোনার দরকার নেই — order-টাই rank।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব `(score, index)` জোড়া max-heap-এ ঢালো। তারপর rank = 1 থেকে শুরু করে একে একে pop করো; প্রথম তিনটার জন্য medal name, বাকিদের জন্য `str(rank)` বসাও — সবসময় pop-এ পাওয়া index-এ। Heapify O(n), n-টা pop প্রতিটা O(log n) — মোট O(n log n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কে কোন medal পাবে" না ভেবে ভাবো "একটা changing set থেকে বারবার max টেনে বের করছি, আর বের হওয়ার order-ই rank।" যখনই কোনো problem বলে "সবচেয়ে বড়/ছোট অনুযায়ী label বা position দাও, কিন্তু answer original জায়গায় চাই", তখন `(value, index)` জোড়া + heap/sort-এর কথা মাথায় আসা উচিত।
### ছবিতে বোঝা {#7-visual-explanation}
`score = [10, 3, 8, 9, 4]` দিয়ে দেখি (max-heap-এ top = সবচেয়ে বড় score, সাথে original index):
```text
score: index0=10 index1=3 index2=8 index3=9 index4=4
max-heap pop order (score, index):
(10, 0) -> rank 1 -> "Gold Medal" -> answer[0]
( 9, 3) -> rank 2 -> "Silver Medal" -> answer[3]
( 8, 2) -> rank 3 -> "Bronze Medal" -> answer[2]
( 4, 4) -> rank 4 -> "4" -> answer[4]
( 3, 1) -> rank 5 -> "5" -> answer[1]
answer = ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `score = [10, 3, 8, 9, 4]`:
1. জোড়া বানাও: `(10,0), (3,1), (8,2), (9,3), (4,4)`; max-heap (negate score) → top = (10,0)
2. pop (10,0) → rank 1 → answer[0] = "Gold Medal"
3. pop (9,3) → rank 2 → answer[3] = "Silver Medal"
4. pop (8,2) → rank 3 → answer[2] = "Bronze Medal"
5. pop (4,4) → rank 4 → answer[4] = "4"
6. pop (3,1) → rank 5 → answer[1] = "5"
7. answer = ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def find_relative_ranks(score):
n = len(score)
answer = [""] * n
# max-heap: score negate করো, সাথে original index
h = [(-s, i) for i, s in enumerate(score)]
heapq.heapify(h) # O(n)-এ heap, top-এ সবচেয়ে বড় score
medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
rank = 1
while h:
_, i = heapq.heappop(h) # বর্তমান সবচেয়ে বড় score-এর index
if rank <= 3:
answer[i] = medals[rank - 1] # প্রথম তিনজন medal পায়
else:
answer[i] = str(rank) # বাকিরা rank-এর সংখ্যা
rank += 1
return answer
# ---- tests ----
assert find_relative_ranks([5, 4, 3, 2, 1]) == ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
assert find_relative_ranks([10, 3, 8, 9, 4]) == ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]
assert find_relative_ranks([1]) == ["Gold Medal"] # একজনই
assert find_relative_ranks([2, 1]) == ["Gold Medal", "Silver Medal"]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `answer = [""] * n` — result array আগে থেকে বানিয়ে রাখি, যাতে index দিয়ে সরাসরি বসানো যায়।
- `h = [(-s, i) for ...]` — প্রতিটা score negate; min-heap-কে max-heap বানানোর trick, সাথে original index।
- `heapq.heapify(h)` — list-টাকে O(n)-এ valid heap বানায়; top-এ সবচেয়ে বড় score।
- `_, i = heapq.heappop(h)` — top pop করে শুধু index নিই (score আর লাগছে না, তাই `_`)।
- `if rank <= 3:` — প্রথম তিনজন medal name পায়; বাকিরা `str(rank)`।
- `answer[i] = ...` — label-টা athlete-এর **original** জায়গায় বসে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`find_relative_ranks([10,3,8,9,4])` section 14-এর dry run মেনে `["Gold Medal","5","Bronze Medal","Silver Medal","4"]` দেয় — assert pass। `[5,4,3,2,1]` already descending, তাই index-গুলো সোজা rank পায়। `[1]` একজনই → "Gold Medal"। `[2,1]` → দুজন → Gold, Silver। চারটে assert pass করার পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — `heapify` O(n), তারপর n-টা pop প্রতিটা O(log n)। সমতুল্যভাবে একটা sort করলেও একই খরচ।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `(score, index)` জোড়ার heap আর result array। heap ছাড়া sort-based solution করলেও index-list O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- max-heap না বানিয়ে সরাসরি heapq ব্যবহার করা — তখন তুমি সবচেয়ে ছোট score-কে Gold দিচ্ছ, উল্টো উত্তর।
- index ভুলে গিয়ে শুধু sorted label list বানানো — তখন answer original order-এ বসে না।
- rank গোনা 0 থেকে শুরু করা — `medals[rank-1]` ভুল index, বা `"3"`-এর জায়গায় `"4"` বসে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `02-arrays-and-strings`-এর "sort by key, keep original index" move, আর `08`-এর `concept.md`-র max-heap-via-negation trick (push/pop)। এটা top-K বা greedy না — বিশুদ্ধ "order মানেই rank" warm-up, যা heap-কে sort-এর বিকল্প হিসেবে দেখায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Largest Element in an Array —