005 — Kth Largest Element in an Array¶

Source¶

Original source: Classic top-K selection
Platform: LeetCode — https://leetcode.com/problems/kth-largest-element-in-an-array/
Topic: heap / priority queue
Difficulty: Medium
Pattern: Top-K (size-k min-heap)
Basic idea inherited from: 08 top-K pattern — size-k min-heap যেটা club-এর দরজা পাহারা দেয়

1. Problem in simple words¶

একটা সংখ্যার array আর একটা সংখ্যা k দেওয়া আছে। তোমাকে k-তম সবচেয়ে বড় element-টা বের করতে হবে — sorted order-এ নয়, distinct value-ও নয়, বরং sorted-descending করলে যেটা k নম্বরে পড়ত সেই value। অর্থাৎ duplicate থাকলেও তারা আলাদা করে গোনা হয়।

nums = [3, 2, 1, 5, 6, 4],  k = 2  ->  2nd largest = 5

2. Which basic idea does this inherit from?¶

ভিত হলো top-K pattern: একটা size-k min-heap। তোমার পুরো sorted array লাগে না — শুধু সবচেয়ে বড় k-টা element ধরে রাখতে হয়, আর তাদের মধ্যে সবচেয়ে ছোটটাই (heap top) হলো উত্তর। এটাই 08-এর "min-heap guards the club door" move।

3. What is the hidden math or logic?¶

লুকানো logic: k-তম largest = সবচেয়ে বড় k-টা element-এর মধ্যে সবচেয়ে ছোটটা। যদি একটা size-k container-এ সবসময় এখন-পর্যন্ত-দেখা সবচেয়ে বড় k-টা element রাখো, তবে container-এর minimum-ই k-তম largest। নতুন element কেবল তখনই ঢোকে যখন সে container-এর বর্তমান minimum-কে হারায়।

4. Which data structure is needed?¶

একটা size-k min-heap। heapq সরাসরি min-heap, আর এখানে আমরা চাই top-এ থাকুক "club-এর দুর্বলতম member" (k largest-দের মধ্যে সবচেয়ে ছোট) — তাই negate-ও করতে হয় না, plain min-heap-ই কাজ করে।

5. Why this data structure fits¶

min-heap-এর top সবসময় তার ভেতরের সবচেয়ে ছোট value। size k রাখলে সেই top-ই হলো "k largest-দের মধ্যে দুর্বলতম" = k-তম largest। প্রতিটা newcomer-কে শুধু top-এর সাথে compare করতে হয় (সব k জনের সাথে না), push/pop O(log k)। মোট O(n log k) — পুরো sort (O(n log n))-এর চেয়ে সস্তা যখন k ছোট, আর stream-এও চলে।

6. Real-life analogy¶

একটা exclusive club-এ ঠিক k জন সদস্য থাকতে পারে। দরজায় দাঁড়িয়ে আছে club-এর সবচেয়ে দুর্বল সদস্য (heap top)। নতুন কেউ এলে তাকে সব সদস্যের সাথে লড়তে হয় না — শুধু এই দুর্বলতমের সাথে। হারালে দুর্বলতম বেরিয়ে যায়, নতুন জন ঢোকে। সবার শেষে দরজায় যে দাঁড়িয়ে, সে-ই k-তম সেরা। সেই "দুর্বলতমকে চট করে দাও" যন্ত্রটাই min-heap।

7. Visual explanation¶

nums = [3, 2, 1, 5, 6, 4], k = 2। size-2 min-heap রাখি (top = দুজন সেরার মধ্যে দুর্বলতম):

nums:  3, 2, 1, 5, 6, 4    k = 2

push 3        -> heap [3]            (size < k)
push 2        -> heap [2, 3]         (size == k, top = 2)
1: 1 > 2? না  -> heap [2, 3]          (rejected)
5: 5 > 2? হ্যাঁ -> pop 2, push 5 -> heap [3, 5]   (top = 3)
6: 6 > 3? হ্যাঁ -> pop 3, push 6 -> heap [5, 6]   (top = 5)
4: 4 > 5? না  -> heap [5, 6]          (rejected)

heap top = 5  ->  2nd largest = 5

8. Example input and output¶

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
Input : nums = [1], k = 1                       -> Output: 1
Input : nums = [2, 1], k = 2                     -> Output: 1   (2nd largest)

9. Brute force thinking¶

প্রথম সরল চিন্তা: পুরো array descending sort করো, তারপর index k-1-এর element নাও।

[3,2,1,5,6,4] -> sort desc -> [6,5,4,3,2,1] -> index 1 -> 5

10. Why brute force is slow¶

পুরো array sort মানে O(n log n), অথচ তোমার শুধু k-তম element লাগছে — পুরো order না। k যখন ছোট (যেমন k=2, n=10⁶), পুরো sort করা বিশাল অপচয়; আর stream-এ data এলে তো পুরো array একসাথে পাওয়াও যায় না।

11. Key observation¶

মূল observation: k-তম largest জানতে তোমার শুধু সবচেয়ে বড় k-টা element track করলেই চলে, পুরো array না। আর তাদের মধ্যে সবচেয়ে ছোটটাই উত্তর — যেটা একটা size-k min-heap-এর top-এ বিনামূল্যে বসে থাকে।

12. Optimized intuition¶

একটা min-heap রাখো। প্রতিটা element push করো, কিন্তু size k ছাড়ালেই top (সবচেয়ে ছোট) pop করে দাও। সব শেষে heap-এ ঠিক k-টা element — সবচেয়ে বড় k-টা — আর top-ই k-তম largest। প্রতিটা op O(log k), মোট O(n log k)।

13. Thinking tweak¶

মোচড়: "k-তম largest খুঁজছি" না ভেবে ভাবো "একটা size-k VIP লিস্ট maintain করছি, আর দরজায় দাঁড়ানো দুর্বলতমই উত্তর।" Counterintuitive অংশ: largest খুঁজতে min-heap লাগে, কারণ একটাই প্রশ্ন matter করে — "তুমি কি আমাদের worst-এর চেয়ে ভালো?"

14. Step-by-step dry run¶

Input nums = [3, 2, 1, 5, 6, 4], k = 2:

push 3 → heap {3} (size 1 < 2)
push 2 → heap {2, 3} (size 2 == k, top = 2)
1: 1 > top(2)? না → reject → heap {2, 3}
5: 5 > 2? হ্যাঁ → heapreplace → pop 2, push 5 → heap {3, 5}, top = 3
6: 6 > 3? হ্যাঁ → heapreplace → pop 3, push 6 → heap {5, 6}, top = 5
4: 4 > 5? না → reject → heap {5, 6}
heap top = 5 → return 5

15. Python solution¶

import heapq

def find_kth_largest(nums, k):
    club = nums[:k]                 # প্রথম k জন বিনা লড়াইয়ে ঢোকে
    heapq.heapify(club)             # min-heap: club[0] = দুর্বলতম member
    for x in nums[k:]:
        if x > club[0]:             # বর্তমান দুর্বলতমকে হারায়?
            heapq.heapreplace(club, x)   # দুর্বলতম pop, x push (এক repair)
    return club[0]                  # দুর্বলতম member = 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([1], 1) == 1
assert find_kth_largest([2, 1], 2) == 1            # 2nd largest = 1
assert find_kth_largest([7, 7, 7], 2) == 7         # duplicate-ও আলাদা গোনা
print("সব test pass!")

16. Line-by-line code explanation¶

club = nums[:k] — প্রথম k-টা element বিনা শর্তে club-এ; এরাই initial top-K candidate।
heapq.heapify(club) — O(k)-এ min-heap; club[0] হয় এই k জনের মধ্যে দুর্বলতম।
for x in nums[k:]: — বাকি element-গুলো একে একে club-এর দরজায় আসে।
if x > club[0]: — newcomer শুধু দুর্বলতমের সাথে লড়ে; হারালে rejected।
heapq.heapreplace(club, x) — দুর্বলতম pop + x push একসাথে, একটাই heap repair (push-then-pop-এর চেয়ে efficient)।
return club[0] — সব শেষে দরজায় দাঁড়ানো দুর্বলতমই k-তম largest।

17. Output walkthrough¶

find_kth_largest([3,2,1,5,6,4],2) section 14-এর dry run মেনে 5 দেয় — assert pass। [3,2,3,1,2,4,5,5,6],4 → top-4 হয় {4,5,5,6}, দুর্বলতম 4। [1],1 → club {1}, top 1। [2,1],2 → দুজনই club-এ, top 1। [7,7,7],2 → duplicate আলাদা গোনা, top 7। পাঁচটা assert pass করার পরে print হয়: সব test pass!।

18. Time complexity¶

O(n log k) — প্রথম k-টার heapify O(k), তারপর বাকি n−k element-এর প্রতিটায় বড়জোর একটা O(log k) replace। k ছোট হলে full sort (O(n log n))-এর চেয়ে অনেক সস্তা।

19. Space complexity¶

O(k) — heap-এ কখনো k-টার বেশি element থাকে না। এটাই top-K-র বড় সুবিধা: n যত বড়ই হোক, memory শুধু k-তে বাঁধা — endless stream-এও চলে।

20. Common mistakes¶

max-heap বানিয়ে n-টা pop করা — কাজ করে, কিন্তু O(n + k log n) আর O(n) space; size-k min-heap বেশি পরিষ্কার আর memory-সাশ্রয়ী।
size guard ভুলে গিয়ে heap বড় হতে দেওয়া — তখন top আর k-তম largest থাকে না।
distinct-largest ভাবা — এটা k-তম largest element, k-তম distinct value না; duplicate আলাদা গোনা।

21. Which basic problem this inherits from¶

ভিত্তি 08-এর top-K pattern (patterns.md Pattern 1) — size-k min-heap, "min-heap guards the club door"। এটাই top-K family-র মূল problem; পরের অনেক problem (frequent elements, closest points) এই একই কঙ্কালে count বা distance যোগ করে।

22. Similar harder problems¶

Top K Frequent Elements — https://leetcode.com/problems/top-k-frequent-elements/ (এই tracker-এর #6)
K Closest Points to Origin — https://leetcode.com/problems/k-closest-points-to-origin/ (#7)
Kth Smallest Element in a Sorted Matrix — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/ (#12)

23. Pattern learned¶

Top-K via size-k min-heap: k largest চাইলে size-k min-heap রাখো; প্রতিটা newcomer শুধু top (দুর্বলতম)-এর সাথে লড়ে। শেষে top = k-তম largest, পুরো heap = top-K। O(n log k), O(k) memory — stream-friendly। (k smallest চাইলে উল্টোটা: size-k max-heap।)

24. Final summary¶

ভবিষ্যতের আমাকে: "k-তম largest / top-K" = size-k min-heap, top-এ দুর্বলতম। newcomer যদি top-কে হারায় তবেই ঢোকে (heapreplace)। মনে রেখো — largest খুঁজতে min-heap, আর দরজায় দাঁড়ানো member-ই উত্তর। এটা top-K-র hello-world, প্রায় চোখ বন্ধ করে লেখা চাই।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

// Node-এ built-in heap নেই, তাই একটা minimal binary MinHeap বানাই
class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]]; i = p;
    }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2; let s = i;
        if (l < a.length && a[l] < a[s]) s = l;
        if (r < a.length && a[r] < a[s]) s = r;
        if (s === i) break;
        [a[s], a[i]] = [a[i], a[s]]; i = s;
      }
    }
    return top;
  }
}

function findKthLargest(nums, k) {
  const club = new MinHeap();        // size-k min-heap: top = দুর্বলতম member
  for (const x of nums) {
    club.push(x);
    if (club.size > k) club.pop();   // k ছাড়ালে দুর্বলতম বাদ
  }
  return club.peek();                // দুর্বলতম = k-তম largest
}

// ---- test cases ----
assert(findKthLargest([3, 2, 1, 5, 6, 4], 2) === 5, "2nd largest");
assert(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) === 4, "4th largest");
assert(findKthLargest([1], 1) === 1, "একক");
assert(findKthLargest([2, 1], 2) === 1, "2nd of two");
assert(findKthLargest([7, 7, 7], 2) === 7, "duplicate আলাদা গোনা");
console.log("সব JS test pass!");

JS টীকা: JS/Node-এ built-in priority queue বা heap নেই (Python-এর heapq-র মতো কিছু নেই), তাই উপরে একটা minimal MinHeap class হাতে লিখতে হয়েছে — push bubble-up করে, pop sift-down করে, দুটোই O(log n)। বিকল্পে ছোট ইনপুটে nums.slice().sort((a,b)=>b-a)[k-1] দিয়েও করা যায় (O(n log n)), কিন্তু size-k heap O(n log k) আর stream-friendly — তাই pattern শেখাতে heap-ই দেখালাম।

26. TypeScript solution (with test cases)¶

class MinHeap {
  private a: number[] = [];
  get size(): number { return this.a.length; }
  peek(): number { return this.a[0]; }
  push(x: number): void {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]]; i = p;
    }
  }
  pop(): number {
    const a = this.a, top = a[0], last = a.pop() as number;
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2; let s = i;
        if (l < a.length && a[l] < a[s]) s = l;
        if (r < a.length && a[r] < a[s]) s = r;
        if (s === i) break;
        [a[s], a[i]] = [a[i], a[s]]; i = s;
      }
    }
    return top;
  }
}

function findKthLargest(nums: number[], k: number): number {
  const club = new MinHeap();
  for (const x of nums) {
    club.push(x);
    if (club.size > k) club.pop();
  }
  return club.peek();
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };

expect(findKthLargest([3, 2, 1, 5, 6, 4], 2) === 5, "5");
expect(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) === 4, "4");
expect(findKthLargest([1], 1) === 1, "একক");
expect(findKthLargest([2, 1], 2) === 1, "1");
expect(findKthLargest([7, 7, 7], 2) === 7, "dup");
console.log("সব TS test pass!");

TS টীকা: private a: number[] heap-এর ভেতরের array লুকিয়ে রাখে আর নিশ্চিত করে এতে শুধু সংখ্যা ঢোকে — ভুল type push করলে compile error। pop()-এর return type number declared, তাই caller-এ আর undefined handle করতে হয় না (আমরা size guard দিয়ে নিশ্চিত করি heap অখালি)। typed heap পুরো top-K logic-কে number-এ আবদ্ধ রাখে।

27. কোথায় কাজে লাগে (real-world use)¶

Leaderboard / top scorers: বিশাল স্ট্রিম থেকে "top k স্কোর" বা "k-তম সেরা" রাখতে size-k heap — পুরো list memory-তে না রেখেই।
Top-N trending / analytics: বিপুল event-stream থেকে সবচেয়ে frequent বা highest-value k-টা item ধরে রাখা (log analysis, recommendation)।
k nearest / k best results: search বা ranking-এ সবচেয়ে প্রাসঙ্গিক k-টা ফলাফল রাখা, বাকি সব sort না করেই।
Streaming percentile / threshold: চলমান data-তে একটা rank-ভিত্তিক cutoff (যেমন "টপ ১০% পেতে কত স্কোর লাগবে") আপডেট রাখা।
Resource throttling: সীমিত k-স্লট (যেমন k সবচেয়ে গুরুত্বপূর্ণ task) ধরে রাখা, নতুন এলে দুর্বলতমকে বাদ দেওয়া।

মূল সুর: পুরো dataset sort করার দরকার নেই যখন শুধু top/bottom-k লাগছে — একটা size-k heap O(n log k)-তে আর সীমিত memory-তে কাজ সারে।

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