012 — Kth Largest Element in an Array¶

Source¶

Original source: Classic capstone interview problem (heap of size k vs quickselect)
Platform: LeetCode — https://leetcode.com/problems/kth-largest-element-in-an-array/
Topic: heaps + sorting/partition
Difficulty: Medium
Pattern: Size-k min-heap (online), অথবা quickselect partition (average O(n))
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 08 heaps (সবচেয়ে ছোট-এর-মধ্যে-বড় k-টা ধরে রাখতে একটা min-heap) আর 03 sorting/partition (quickselect-এ pivot দিয়ে array-কে partition করা, যা quicksort-এর অর্ধেক)। দুই tool জোড়া লাগলেই এই problem-এর দুই রকম সমাধান।

1. Problem in simple words¶

তোমাকে একটা integer array আর একটা সংখ্যা k দেওয়া। তোমার কাজ: array-টা যদি বড় থেকে ছোট সাজাতে, তাহলে k-তম স্থানে যে সংখ্যাটা থাকত, সেটা বের করা — মানে k-তম সবচেয়ে বড় element। সাবধান: এটা k-তম আলাদা (distinct) সংখ্যা নয়, ডুপ্লিকেট গুনে নিয়েই k-তম বড়।

nums = [3, 2, 1, 5, 6, 4], k = 2
বড় থেকে সাজালে : [6, 5, 4, 3, 2, 1]
2nd largest      : 5

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

08 heaps থেকে: একটা size-k min-heap ধরা — এতে সবসময় "এ পর্যন্ত দেখা সবচেয়ে বড় k-টা" থাকে, আর heap-এর top (সবচেয়ে ছোট) হলো এই k-টার সবচেয়ে ছোটটা, অর্থাৎ k-তম largest।
03 sorting/partition থেকে: quickselect — quicksort-এর partition step ধার করে, কিন্তু দুই দিকেই recurse না করে শুধু যে দিকে উত্তর আছে সেদিকে যাওয়া।

একা heap দেয় "টপ-k ধরে রাখার" online ক্ষমতা; একা partition দেয় average O(n)-এ একটা order statistic বের করার ক্ষমতা। দুটো জানলে দুই trade-off-ই হাতে।

3. What is the hidden math or logic?¶

লুকানো logic দুটো: (১) heap পথে — size-k min-heap-এর root সবসময় k-তম largest, কারণ আমরা শুধু সবচেয়ে বড় k-টা রাখি আর তার মধ্যে সবচেয়ে ছোটটা root-এ থাকে। (২) quickselect পথে — partition করার পর pivot তার চূড়ান্ত sorted জায়গায় বসে; সেই index দেখে বলে দেওয়া যায় উত্তর pivot-এই, নাকি বাঁ/ডান অংশে। "k-তম largest" = "index n-k-তম smallest", এই rank-translation-টাই চাবি।

4. Which data structure is needed?¶

দুটো রাস্তা:

Heap পথ: Python-এর heapq (min-heap), size k-তে আটকানো (08 heaps)।
Quickselect পথ: শুধু input array নিজেই, in-place partition (03 sorting/partition) — extra structure লাগে না।

5. Why this data structure fits¶

min-heap-এ push আর pop দুটোই O(log k), তাই k ছোট হলে (বা data stream-এ এলে) এটা চমৎকার — পুরো array sort না করেই (যা O(n log n)) আমরা O(n log k)-এ top-k পাই, আর root-এ O(1)-এ k-তম largest। অন্যদিকে quickselect partition (03)-কে কাজে লাগিয়ে average O(n)-এ একই উত্তর দেয়, কারণ প্রতিবার অর্ধেক অংশ ফেলে দিই — পুরো sort-এর মতো দুই দিকে নয়। তাই heap (08) দেয় st-friendly online সমাধান, partition (03) দেয় দ্রুততম average সমাধান — দুটোই problem-টায় নিখুঁত খাপ খায়।

6. Real-life analogy¶

ভাবো তুমি একটা পরীক্ষার শীর্ষ-3 জনকে মনে রাখতে চাও, কিন্তু সব খাতা একসাথে সাজাতে চাও না। তুমি একটা ছোট তিন-জনের "leaderboard" রাখো, যেখানে সবচেয়ে নিচের জন সবার আগে চোখে পড়ে। নতুন খাতা এলে দেখো — এটা কি ওই নিচের জনের চেয়ে ভালো? হলে নিচের জনকে বাদ দিয়ে নতুনকে ঢোকাও। সব খাতা শেষে leaderboard-এর সবচেয়ে নিচের জনই হলো 3rd best। এই "সবচেয়ে দুর্বলটা সবার আগে দেখা যায়" বোর্ডটাই min-heap।

7. Visual explanation¶

nums = [3,2,1,5,6,4], k = 2 — size-2 min-heap গড়ি (heap-এ top = সবচেয়ে ছোট):

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

top (সবচেয়ে ছোট 2-টার মধ্যে) = 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   # ডুপ্লিকেট গুনে নিয়ে

Edge case 1 (k = 1, সবচেয়ে বড়): nums=[7,7,7], k=1 -> 7
Edge case 2 (k = n, সবচেয়ে ছোট): nums=[2,1], k=2  -> 1
Edge case 3 (একটা element): nums=[1], k=1          -> 1

9. Brute force thinking¶

প্রথম সরল চিন্তা: পুরো array-টা বড় থেকে ছোট sort করো, তারপর k-তম element (index k-1) তুলে নাও।

sort করো (descending)
return nums[k-1]
# অথবা ascending sort করে return nums[n-k]

10. Why brute force is slow¶

পুরো sort O(n log n) — কিন্তু আমরা তো পুরো order চাই না, শুধু একটামাত্র position চাই। তাই অপ্রয়োজনীয় কাজ হচ্ছে: ছোট দিকের সব element-ও নিখুঁত sorted হয়ে যাচ্ছে, যেগুলো লাগবেই না। heap (08) এটাকে O(n log k)-এ আর quickselect (03) average O(n)-এ নামায়, কারণ তারা শুধু দরকারি অংশটুকুই সাজায়।

11. Key observation¶

মূল observation: "k-তম largest" জানতে পুরো array sorted করার দরকার নেই — শুধু সবচেয়ে বড় k-টা element আর তাদের মধ্যে সবচেয়ে ছোটটা জানলেই হয়। একটা size-k min-heap ঠিক সেই k-টাই ধরে রাখে আর সবচেয়ে ছোটটা (= উত্তর) root-এ রাখে। আর quickselect-এ partition-এর পর pivot-এর index বলে দেয় উত্তর কোন দিকে — এক দিক পুরো বাদ। এই এক চিন্তাই কাজ কমিয়ে দেয়।

12. Optimized intuition¶

Heap পথ: একটা min-heap-এ প্রথম k element ঢোকাও। তারপর বাকি প্রতিটা element-কে heap-এর top (সবচেয়ে ছোট)-এর সাথে তুলনা করো — বড় হলে top pop করে নতুনকে push। শেষে top-ই k-তম largest। Quickselect পথ: target index n-k (ascending-এ k-তম largest-এর জায়গা)। random pivot দিয়ে partition করো; pivot যদি target-এ বসে — পেলাম; নাহলে যে দিকে target সে দিকেই recurse, অন্য দিক ফেলে দাও।

13. Thinking tweak¶

মোচড়: "সব সাজিয়ে k-তমটা নেব" ভাবার বদলে ভাবো "আমার তো মাত্র k-টা বড় element দরকার — বাকিদের নিয়ে মাথা ঘামাব কেন?" পুরো sort-এর জায়গায় হয় একটা ছোট k-আকারের bucket (heap) রাখো, নয় partition দিয়ে অর্ধেক করে ফেলে দাও।

14. Step-by-step dry run¶

Heap পথ, nums = [3,2,1,5,6,4], k = 2:

heap-এ প্রথম 2-টা: push 3, push 2 → heap = [2, 3] (top 2)
1: 1 > 2? না → skip; heap = [2, 3]
5: 5 > 2? হ্যাঁ → pop 2, push 5; heap = [3, 5]
6: 6 > 3? হ্যাঁ → pop 3, push 6; heap = [5, 6]
4: 4 > 5? না → skip; heap = [5, 6]
শেষ → top = 5 → return 5

15. Python solution¶

import heapq

def find_kth_largest(nums, k):
    heap = []                      # size-k min-heap (08 heaps)
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:          # k-এর বেশি হলে সবচেয়ে ছোটটা ফেলে দাও
            heapq.heappop(heap)
    return heap[0]                 # top = k-টা বড়-এর মধ্যে সবচেয়ে ছোট = 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([7, 7, 7], 1) == 7                      # k = 1, সবচেয়ে বড়
assert find_kth_largest([2, 1], 2) == 1                         # k = n, সবচেয়ে ছোট
assert find_kth_largest([1], 1) == 1                            # একটা element
assert find_kth_largest([-1, -1, 0], 1) == 0                    # negative সহ
print("সব test pass!")

16. Line-by-line code explanation¶

heap = [] — খালি min-heap; Python-এর heapq default-এ min-heap (08 heaps)।
for x in nums — প্রতিটা element একবার দেখি (single pass)।
heapq.heappush(heap, x) — element ঢোকাই, O(log k)।
if len(heap) > k: heapq.heappop(heap) — size k-এর বেশি হলে সবচেয়ে ছোটটা (top) বের করে দাও; ফলে heap-এ সবসময় সবচেয়ে বড় k-টাই থাকে।
return heap[0] — heap-এর top হলো এই k-টার সবচেয়ে ছোট = k-তম largest।

17. Output walkthrough¶

[3,2,1,5,6,4], k=2-এ heap গড়তে গড়তে এক সময় [5,6] হয় (সবচেয়ে বড় 2-টা), top 5; return 5 — assert pass। ডুপ্লিকেট-ওয়ালা [3,2,3,1,2,4,5,5,6], k=4-এ সবচেয়ে বড় 4-টা {6,5,5,4}, তার সবচেয়ে ছোট 4 → সঠিক। k=1, k=n, একটা element, negative — সব case ঠিক। শেষে print: সব test pass!।

18. Time complexity¶

O(n log k) (heap পথ) — n-টা element, প্রতিটায় O(log k) push/pop। Quickselect পথে average O(n), worst-case O(n^2) (random pivot সেই worst এড়ায়)।

19. Space complexity¶

O(k) (heap পথ) — heap সর্বোচ্চ k element রাখে। Quickselect in-place হলে O(1) extra (recursion stack বাদে)।

20. Common mistakes¶

max-heap বানিয়ে n বার pop করা (O(n log n)) — তখন heap-এর সুবিধাই থাকে না; size-k min-heap-ই আসল চাল।
"k-তম largest" আর "k-তম distinct largest" গুলিয়ে ফেলা — এখানে ডুপ্লিকেট গোনা হয়।
index off-by-one: ascending sort-এ k-তম largest হলো nums[n-k], nums[k-1] নয় (descending হলে উল্টো)।
quickselect-এ fixed pivot (যেমন সবসময় শেষ element) নেওয়া — already-sorted input-এ O(n^2); random pivot নাও।

21. Which basic problem this inherits from¶

ভিত্তি: heap operations / size-limited heap (08 heaps, ../../08-heaps-and-priority-queues/) + quicksort-এর partition step থেকে quickselect (03 sorting, ../../03-searching-and-sorting/)। এই দুটো cold জানা থাকলে দুই রকম সমাধানই নিজে থেকে আসে।

22. Similar harder problems¶

Kth Smallest Element in a Sorted Matrix (heap বা binary search on value) — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
Find Median from Data Stream (দুটো heap-এর balance) — https://leetcode.com/problems/find-median-from-data-stream/
K Closest Points to Origin (একই size-k heap idea) — https://leetcode.com/problems/k-closest-points-to-origin/
Top K Frequent Elements (count + heap) — https://leetcode.com/problems/top-k-frequent-elements/

23. Pattern learned¶

Size-k heap / quickselect for order statistics: পুরো sort না করে, হয় একটা size-k min-heap-এ top-k ধরে রেখে root পড়া, নয় partition দিয়ে অর্ধেক ফেলে average O(n)-এ k-তম element বের করা। "k-তম largest/smallest / top-k"-জাতীয় problem-এর canonical জোড়া।

24. Final summary¶

ভবিষ্যতের আমাকে: "k-তম largest/smallest" বা "top-k" শুনলেই দুটো অস্ত্র মনে করবে — (১) size-k min-heap (online, O(n log k), root = উত্তর) আর (২) quickselect (average O(n), in-place, target index n-k)। min-heap-টা min কেন তা ভুলো না, আর quickselect-এ random pivot নিয়ো (worst-case এড়াতে)। interviewer "stream হলে?" জিজ্ঞেস করলে heap-পথ বলবে।

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