002 — Kth Largest Element in a Stream¶

Source¶

Original source: Classic top-K streaming exercise
Platform: LeetCode — https://leetcode.com/problems/kth-largest-element-in-a-stream/
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

1. Problem in simple words¶

একটা class বানাও যেটা একটা চলমান stream-এ সবসময় k-তম largest সংখ্যাটা বলতে পারে। Constructor-এ পাবে k আর শুরুর কিছু সংখ্যা। তারপর বারবার add(val) ডাকা হবে — প্রতিবার নতুন সংখ্যা যোগ হওয়ার পরে এ পর্যন্ত দেখা সব সংখ্যার মধ্যে k-তম largest টা return করতে হবে। মনে রেখো, "k-তম largest" মানে duplicate ধরে গোনা — distinct না।

k = 3, শুরু = [4, 5, 8, 2]
add(3) -> 4    add(5) -> 5    add(10) -> 5    add(9) -> 8    add(4) -> 8

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 জমানোর দরকারই নেই।

6. Real-life analogy¶

একটা exclusive club-এর দরজায় bouncer ভাবো, ভেতরে ঠিক k-টা সিট। সবচেয়ে দুর্বল member দরজার সবচেয়ে কাছে দাঁড়িয়ে। নতুন কেউ এলে bouncer শুধু তাকে দরজার ওই দুর্বলতম-এর সাথে মাপে — সবার সাথে না। নতুন লোক বড় হলে দুর্বলতম বেরিয়ে যায়, নতুন লোক ঢোকে। দরজায় দাঁড়ানো লোকটাই তোমার k-তম largest।

7. Visual explanation¶

k = 3, শুরু [4, 5, 8, 2] → size-3 min-heap রাখি (top = k-তম largest):

শুরু: সব ঢেলে দিয়ে 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

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সংখ্যা একটা list-এ জমাও। add-এর সময় পুরো list sort করে নিচ থেকে k-তম বড়টা (sorted_list[-k]) ফেরত দাও।

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

14. Step-by-step dry run¶

KthLargest(3, [4, 5, 8, 2]):

push 4,5,8,2 → size 4 > 3 → pop top (2) → heap {4,5,8}, top = 4
add(3): push 3 → size 4 → pop min (3) → heap {4,5,8}, return 4
add(5): push 5 → size 4 → pop min (4) → heap {5,5,8}, return 5
add(10): push 10 → size 4 → pop min (5) → heap {5,8,10}, return 5
add(9): push 9 → size 4 → pop min (5) → heap {8,9,10}, return 8
add(4): push 4 → size 4 → pop min (4) → heap {8,9,10}, return 8

15. Python solution¶

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।

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

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] দুটো আলাদা)।

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 — 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)
Find Median from Data Stream — https://leetcode.com/problems/find-median-from-data-stream/ (#18)

23. Pattern learned¶

Top-K via size-k heap: k largest লাগলে size-k min-heap রাখো; নতুন প্রতিটা item শুধু top (দুর্বলতম)-এর সাথে লড়ে। top-ই k-তম largest। stream হলে heap-টা persistent state হয়ে যায়।

24. Final summary¶

ভবিষ্যতের আমাকে: "চলমান stream + k-তম largest" = একটা size-k min-heap object-এর ভেতরে। নতুন এলে push, ভরে গেলে top pop, উত্তর = heap[0]। মন্ত্র মনে রেখো — min-heap guards the door — largest খুঁজতে min-heap, এটাই pattern-এর প্রাণ।

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