003 — Relative Ranks¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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 বের করা

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

কতগুলো 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"]

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

চেনা উদাহরণে বোঝা¶

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত হলো sorting, কিন্তু index মনে রেখে। তোমাকে শুধু সাজালেই হবে না — সাজানোর পরে প্রতিটা score আবার তার আসল জায়গায় বসাতে হবে। তাই value-র সাথে তার original index-টা একসাথে নিয়ে চলা — এটা 02-arrays-and-strings-এর "sort by key, remember where it came from" move।

ভেতরের যুক্তি¶

লুকানো logic খুব সরল: descending order-এ position-ই হলো rank। সবচেয়ে বড় score = rank 1, পরেরটা = rank 2, ইত্যাদি। প্রথম তিনটা rank-এর জন্য আলাদা নাম, বাকিগুলোর জন্য সংখ্যাটাই। তাই কাজটা দাঁড়ায়: প্রতিটা score বড় থেকে ছোট দিকে কত নম্বরে আছে সেটা বের করা, আর সেই অনুযায়ী label বসানো।

কী দিয়ে তথ্য রাখব¶

একটা max-heap (বা সমতুল্যভাবে একটা sort)। আমরা (score, index) জোড়াগুলো max-heap-এ রাখব, যাতে বারবার pop করলেই বড় থেকে ছোট order-এ score বেরিয়ে আসে — আর সাথে আসা index বলে দেয় answer কোথায় বসাতে হবে।

এটি কেন উপযুক্ত¶

Heap-এর top সবসময় বর্তমান সবচেয়ে বড় score। বারবার pop করলে rank 1, 2, 3, … order-এই পাও — ঠিক যে order-এ label বসাতে হবে। প্রতিটা pop O(log n), আর সাথে আসা index মানে result array-তে সরাসরি লেখা যায়, আলাদা lookup লাগে না।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা 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 দেখা।

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা element-এর rank বের করতে পুরো array scan মানে O(n) প্রতিজনের জন্য, মোট O(n²)। অথচ একবার সাজিয়ে নিলেই সব rank একসাথে বেরিয়ে আসে — প্রতিবার আলাদা করে গুনে দেখা নিখাদ অপচয়।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: rank মানে শুধুই descending order-এ position। তাই একটাই sort (বা heap pop sequence) সব rank একসাথে দিয়ে দেয়। আলাদা করে প্রতিজনের জন্য গোনার দরকার নেই — order-টাই rank।

আরও কম কাজে সমাধান¶

সব (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)।

ভাবনার পরিবর্তন¶

মোচড়: "কে কোন medal পাবে" না ভেবে ভাবো "একটা changing set থেকে বারবার max টেনে বের করছি, আর বের হওয়ার order-ই rank।" যখনই কোনো problem বলে "সবচেয়ে বড়/ছোট অনুযায়ী label বা position দাও, কিন্তু answer original জায়গায় চাই", তখন (value, index) জোড়া + heap/sort-এর কথা মাথায় আসা উচিত।

ছবিতে বোঝা¶

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

ছোট input-এ ধাপে ধাপে¶

Input score = [10, 3, 8, 9, 4]:

জোড়া বানাও: (10,0), (3,1), (8,2), (9,3), (4,4); max-heap (negate score) → top = (10,0)
pop (10,0) → rank 1 → answer[0] = "Gold Medal"
pop (9,3) → rank 2 → answer[3] = "Silver Medal"
pop (8,2) → rank 3 → answer[2] = "Bronze Medal"
pop (4,4) → rank 4 → answer[4] = "4"
pop (3,1) → rank 5 → answer[1] = "5"
answer = ["Gold Medal","5","Bronze Medal","Silver Medal","4"]

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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

খরচ ও সাধারণ ভুল¶

সময়¶

O(n log n) — heapify O(n), তারপর n-টা pop প্রতিটা O(log n)। সমতুল্যভাবে একটা sort করলেও একই খরচ।

অতিরিক্ত জায়গা¶

O(n) — (score, index) জোড়ার heap আর result array। heap ছাড়া sort-based solution করলেও index-list O(n)।

যে ভুলগুলো এড়াতে হবে¶

max-heap না বানিয়ে সরাসরি heapq ব্যবহার করা — তখন তুমি সবচেয়ে ছোট score-কে Gold দিচ্ছ, উল্টো উত্তর।
index ভুলে গিয়ে শুধু sorted label list বানানো — তখন answer original order-এ বসে না।
rank গোনা 0 থেকে শুরু করা — medals[rank-1] ভুল index, বা "3"-এর জায়গায় "4" বসে।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি 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-এর বিকল্প হিসেবে দেখায়।

পরের অনুশীলন¶

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)

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "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।