003 — Relative Ranks

Source

• Original source: Classic heap / sorting warm-up
• Platform: LeetCode — https://leetcode.com/problems/relative-ranks/
• Topic: heap / priority queue
• Difficulty: Easy
• Pattern: Heap / sorting warm-up
• Basic idea inherited from: 02-arrays-and-strings sorting — value-কে original index মনে রেখে order বের করা

1. Problem in simple words

কতগুলো athlete-এর score দেওয়া আছে, সব আলাদা। সবচেয়ে বেশি score পায় "Gold Medal", তার পরেরটা "Silver Medal", তার পরেরটা "Bronze Medal"। বাকি সবাই তাদের rank-এর সংখ্যাটাই string হিসেবে পায় — চতুর্থ হলে "4", পঞ্চম হলে "5", এভাবে। শেষে প্রতিটা athlete-এর rank তার নিজের original জায়গায় ফেরত দিতে হবে, একটা list of string-এ।

score = [5, 4, 3, 2, 1]  ->  ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

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 লাগে না।

6. Real-life analogy

Sports day-র শেষে judge স্কোরশিট হাতে নিয়ে বসেছেন। তিনি বারবার "এখন সবচেয়ে বেশি কে?" জিজ্ঞেস করে একজন করে ডেকে medal বা position number দিচ্ছেন — Gold, Silver, Bronze, তারপর 4, 5, 6… প্রতিটা athlete-এর নাম (এখানে original index) তিনি মনে রাখছেন, যাতে result শিটে ঠিক জায়গায় বসাতে পারেন। সেই "বারবার সবচেয়ে বড় দাও" যন্ত্রটাই heap।

7. Visual explanation

score = [10, 3, 8, 9, 4] দিয়ে দেখি (max-heap-এ top = সবচেয়ে বড় score, সাথে original index):

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"]

8. Example input and output

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"]

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা score-এর জন্য পুরো array scan করে দেখো তার চেয়ে বড় কতগুলো আছে — সেই count + 1 হলো তার rank। তারপর rank অনুযায়ী label বসাও।

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-এর কথা মাথায় আসা উচিত।

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"]

15. Python solution

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 জায়গায় বসে।

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!।

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" বসে।

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 — https://leetcode.com/problems/kth-largest-element-in-an-array/ (এই tracker-এর #5)
• Top K Frequent Elements — https://leetcode.com/problems/top-k-frequent-elements/ (#6)
• Sort Characters By Frequency — https://leetcode.com/problems/sort-characters-by-frequency/ (#8)

23. Pattern learned

Heap-as-sorted-order: যখন তোমার দরকার শুধু "বড় থেকে ছোট order, আর সেই order-ই answer", তখন (value, index) জোড়া max-heap-এ ঢেলে pop করতে থাকো। এটা top-K-র পূর্বসূরি — পার্থক্য শুধু এখানে সবাইকে দরকার, কিছু k জনকে না।

24. Final summary

ভবিষ্যতের আমাকে: "rank/medal/position দাও, কিন্তু answer original জায়গায়" = (value, index) জোড়া + max-heap (বা sort)। pop order-ই rank; index বলে কোথায় বসাতে হবে। heap এখানে sort-এর সহজ বিকল্প — মনে রেখো, order নিজেই উত্তর।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।