69:T550,import heapq from typing import List def find_kth_largest(nums: List[int], k: int) -> int: """ Find the k-th largest element using a min-heap of size k. Time Complexity: O(n log k) Space Complexity: O(k) The heap maintains the k largest elements seen so far. Its root (minimum) is the k-th largest overall. """ # Python's heapq is a min-heap by default - perfect for this problem! min_heap = [] for num in nums: if len(min_heap) < k: # Phase 1: Fill the heap with first k elements heapq.heappush(min_heap, num) elif num > min_heap[0]: # Phase 2: Replace minimum if current is larger # heapreplace is more efficient than pop + push heapq.heapreplace(min_heap, num) # If num <= min_heap[0], skip it - can't be in top k # The root of min-heap is the k-th largest return min_heap[0] # Example usage nums = [3, 2, 1, 5, 6, 4] k = 2 result = find_kth_largest(nums, k) print(f"The {k}th largest element is: {result}") # Output: 5 # Trace through the algorithm: # Process 3: heap = [3] # Process 2: heap = [2, 3] (k=2 elements now) # Process 1: 1 < 2, skip # Process 5: 5 > 2, replace: heap = [3, 5] # Process 6: 6 > 3, replace: heap = [5, 6] # Process 4: 4 < 5, skip # Final heap minimum = 5 = 2nd largest ✓6a:T48b,import java.util.PriorityQueue; public class KthLargestElement { /** * Find the k-th largest element using a min-heap of size k. * * Time Complexity: O(n log k) * Space Complexity: O(k) */ public static int findKthLargest(int[] nums, int k) { // PriorityQueue in Java is a min-heap by default PriorityQueue minHeap = new PriorityQueue<>(); for (int num : nums) { if (minHeap.size() < k) { // Phase 1: Fill the heap with first k elements minHeap.offer(num); } else if (num > minHeap.peek()) { // Phase 2: Replace minimum if current is larger minHeap.poll(); minHeap.offer(num); } // If num <= minHeap.peek(), skip it } // The root of min-heap is the k-th largest return minHeap.peek(); } public static void main(String[] args) { int[] nums = {3, 2, 1, 5, 6, 4}; int k = 2; int result = findKthLargest(nums, k); System.out.println("The " + k + "th largest: " + result); // 5 } }6b:T80f,// Using a simple MinHeap implementation class MinHeap { private heap: number[] = []; get size(): number { return this.heap.length; } peek(): number | undefined { return this.heap[0]; } push(val: number): void { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop(): number | undefined { if (this.heap.length === 0) return undefined; const min = this.heap[0]; const last = this.heap.pop()!; if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return min; } replace(val: number): number { const min = this.heap[0]; this.heap[0] = val; this.bubbleDown(0); return min; } private bubbleUp(i: number): void { while (i > 0) { const parent = Math.floor((i - 1) / 2); if (this.heap[parent] <= this.heap[i]) break; [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]; i = parent; } } private bubbleDown(i: number): void { const n = this.heap.length; while (true) { let smallest = i; const left = 2 * i + 1, right = 2 * i + 2; if (left < n && this.heap[left] < this.heap[smallest]) smallest = left; if (right < n && this.heap[right] < this.heap[smallest]) smallest = right; if (smallest === i) break; [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]]; i = smallest; } } } function findKthLargest(nums: number[], k: number): number { const minHeap = new MinHeap(); for (const num of nums) { if (minHeap.size < k) { minHeap.push(num); } else if (num > minHeap.peek()!) { minHeap.replace(num); } } return minHeap.peek()!; } // Example const nums = [3, 2, 1, 5, 6, 4]; const k = 2; console.log(`The ${k}th largest: ${findKthLargest(nums, k)}`); // 56c:T50a,import heapq from typing import List def find_kth_smallest(nums: List[int], k: int) -> int: """ Find the k-th smallest element using a max-heap of size k. Python's heapq is a min-heap, so we negate values to simulate max-heap. Time Complexity: O(n log k) Space Complexity: O(k) """ max_heap = [] # Will store negated values for num in nums: if len(max_heap) < k: # Phase 1: Fill the heap with first k elements (negated) heapq.heappush(max_heap, -num) elif num < -max_heap[0]: # num < current maximum # Phase 2: Replace maximum if current is smaller heapq.heapreplace(max_heap, -num) # If num >= -max_heap[0], skip it - can't be in bottom k # The root of max-heap (negated) is the k-th smallest return -max_heap[0] # Example usage nums = [3, 2, 1, 5, 6, 4] k = 2 result = find_kth_smallest(nums, k) print(f"The {k}th smallest element is: {result}") # Output: 2 # Trace: # Process 3: heap = [-3] → represents max-heap [3] # Process 2: heap = [-3, -2] → max-heap [3, 2] # Process 1: 1 < 3, replace: heap = [-2, -1] → max-heap [2, 1] # Process 5: 5 > 2, skip # Process 6: 6 > 2, skip # Process 4: 4 > 2, skip # Final: -heap[0] = 2 = 2nd smallest ✓6d:T539,import heapq from typing import List def find_kth_largest_optimized(nums: List[int], k: int) -> int: """ Optimized version that uses the smaller heap. If k > n/2, it's more efficient to find (n-k+1)th smallest using a max-heap of size (n-k+1). This ensures heap size is at most ceil(n/2), reducing worst-case operations. """ n = len(nums) # Use the more efficient formulation if k > n // 2: # Find (n-k+1)th smallest instead k_small = n - k + 1 max_heap = [] for num in nums: if len(max_heap) < k_small: heapq.heappush(max_heap, -num) elif num < -max_heap[0]: heapq.heapreplace(max_heap, -num) return -max_heap[0] else: # Standard min-heap approach for k-th largest min_heap = [] for num in nums: if len(min_heap) < k: heapq.heappush(min_heap, num) elif num > min_heap[0]: heapq.heapreplace(min_heap, num) return min_heap[0] # Example: Finding 999,999th largest in 1,000,000 elements # Without optimization: heap of 999,999 elements # With optimization: heap of 2 elements (finding 2nd smallest) nums = list(range(1_000_000)) print(find_kth_largest_optimized(nums, 999_999)) # Much faster!6e:T7a6,import heapq from typing import Optional class KthLargestStream: """ Maintains the k-th largest element in a stream. Supports: - add(val): O(log k) - Add a new element - get_kth(): O(1) - Get current k-th largest Use case: Real-time leaderboard, percentile tracking, top-k monitoring """ def __init__(self, k: int, initial_nums: list[int] = None): """ Initialize with k and optionally some initial numbers. """ self.k = k self.min_heap = [] if initial_nums: for num in initial_nums: self.add(num) def add(self, val: int) -> Optional[int]: """ Add a new value to the stream. Returns the current k-th largest (or None if < k elements). """ if len(self.min_heap) < self.k: heapq.heappush(self.min_heap, val) elif val > self.min_heap[0]: heapq.heapreplace(self.min_heap, val) return self.get_kth() def get_kth(self) -> Optional[int]: """ Get the current k-th largest. Returns None if fewer than k elements have been seen. """ if len(self.min_heap) < self.k: return None return self.min_heap[0] # Example: Real-time stock price monitoring # Track the 3rd highest price seen throughout the day tracker = KthLargestStream(k=3) prices = [105.2, 102.8, 108.5, 101.3, 110.0, 107.2, 112.5] for price in prices: kth = tracker.add(price) print(f"New price: {price:>6.1f} | 3rd highest so far: {kth}") # Output: # New price: 105.2 | 3rd highest so far: None # New price: 102.8 | 3rd highest so far: None # New price: 108.5 | 3rd highest so far: 102.8 # New price: 101.3 | 3rd highest so far: 102.8 # New price: 110.0 | 3rd highest so far: 105.2 # New price: 107.2 | 3rd highest so far: 107.2 # New price: 112.5 | 3rd highest so far: 108.56f:T4c7,import java.util.PriorityQueue; public class KthLargestStream { private final int k; private final PriorityQueue minHeap; public KthLargestStream(int k, int[] initialNums) { this.k = k; this.minHeap = new PriorityQueue<>(); if (initialNums != null) { for (int num : initialNums) { add(num); } } } public Integer add(int val) { if (minHeap.size() < k) { minHeap.offer(val); } else if (val > minHeap.peek()) { minHeap.poll(); minHeap.offer(val); } return getKth(); } public Integer getKth() { return minHeap.size() < k ? null : minHeap.peek(); } // LeetCode 703: Kth Largest Element in a Stream public static void main(String[] args) { KthLargestStream tracker = new KthLargestStream( 3, new int[]{4, 5, 8, 2} ); System.out.println(tracker.add(3)); // 4 System.out.println(tracker.add(5)); // 5 System.out.println(tracker.add(10)); // 5 System.out.println(tracker.add(9)); // 8 System.out.println(tracker.add(4)); // 8 } }70:T6a6,import random from typing import List def quickselect(nums: List[int], k: int) -> int: """ Find k-th largest using QuickSelect algorithm. Time: O(n) average, O(n²) worst case Space: O(1) extra (modifies input) Note: Modifies the input array! """ # Convert to 0-indexed position from end target_idx = len(nums) - k def partition(left: int, right: int, pivot_idx: int) -> int: """Partition around pivot, return final pivot position.""" pivot = nums[pivot_idx] # Move pivot to end nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] store_idx = left for i in range(left, right): if nums[i] < pivot: nums[store_idx], nums[i] = nums[i], nums[store_idx] store_idx += 1 # Move pivot to final position nums[right], nums[store_idx] = nums[store_idx], nums[right] return store_idx def select(left: int, right: int) -> int: """Recursively select until target found.""" if left == right: return nums[left] # Random pivot for O(n) expected time pivot_idx = random.randint(left, right) pivot_idx = partition(left, right, pivot_idx) if target_idx == pivot_idx: return nums[pivot_idx] elif target_idx < pivot_idx: return select(left, pivot_idx - 1) else: return select(pivot_idx + 1, right) return select(0, len(nums) - 1) # Example nums = [3, 2, 1, 5, 6, 4] k = 2 result = quickselect(nums.copy(), k) # Copy to preserve original print(f"The {k}th largest: {result}") # 571:T680,import heapq from collections import Counter from typing import List def top_k_frequent(nums: List[int], k: int) -> List[int]: """ LeetCode 347: Top K Frequent Elements Return the k most frequent elements. Uses min-heap of size k, keyed by frequency. Time: O(n log k) Space: O(n) for counter + O(k) for heap """ # Count frequencies freq = Counter(nums) # Min-heap storing (frequency, element) # We want k highest frequencies, so use min-heap of size k min_heap = [] for num, count in freq.items(): if len(min_heap) < k: heapq.heappush(min_heap, (count, num)) elif count > min_heap[0][0]: heapq.heapreplace(min_heap, (count, num)) # Extract elements (not frequencies) return [num for count, num in min_heap] def k_closest_points(points: List[List[int]], k: int) -> List[List[int]]: """ LeetCode 973: K Closest Points to Origin Return k points closest to origin (0, 0). Uses max-heap of size k, keyed by distance. Time: O(n log k) Space: O(k) """ # Max-heap storing (-distance_squared, point) # We want k smallest distances, so use max-heap of size k max_heap = [] for x, y in points: dist_sq = x*x + y*y if len(max_heap) < k: heapq.heappush(max_heap, (-dist_sq, [x, y])) elif dist_sq < -max_heap[0][0]: heapq.heapreplace(max_heap, (-dist_sq, [x, y])) return [point for dist, point in max_heap] # Examples print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2] print(k_closest_points([[1,3],[-2,2]], 1)) # [[-2, 2]]62:{"json":{"id":"seed_5a2a5c818adeed70eeb1b6409a68fccc","slug":"common-heap-patterns","category":"Data Structures & Algorithms","topic":"Common Heap Patterns & Problem Types","title":"Common Heap Patterns & Problem Types","description":"Master the essential heap patterns that appear repeatedly in algorithmic problems. Learn to recognize and solve k-th element problems, merge k sorted lists, median maintenance, and scheduling applications using heaps.","difficulty":"INTERMEDIATE","estimatedMinutes":180,"pages":[{"id":"seed_8b245136d7f61f10e4a1da90b3eee5ed","title":"Finding the K-th Largest/Smallest","order":0,"content":[{"id":"opening-hook","title":"The Order Statistics Problem","content":[{"data":{"content":"In a dataset of a million user transactions, which one ranks exactly at the 99th percentile? Among billions of sensor readings, what's the 10th smallest outlier? Finding not the extreme, but a *specific rank* within data is one of the most fundamental and frequently encountered problems in computing.\n\nThis is the **order statistics problem**—and more specifically, finding the k-th largest or k-th smallest element. Unlike finding the minimum or maximum (which heaps solve trivially), finding an arbitrary order statistic requires careful algorithmic thinking.\n\nWhy not just sort the data? You could—but at O(n log n), sorting is overkill when you only need one specific rank. And what if the data is streaming in continuously? Sorting becomes impossible. Heaps offer an elegant, efficient solution that works for both static and streaming data, achieving O(n log k) time—a dramatic improvement when k is much smaller than n."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will understand why heaps are uniquely suited for k-th element problems, master the counterintuitive technique of using a min-heap to find the k-th largest (and vice versa), analyze the time and space complexity trade-offs, and recognize this pattern in disguised problem variations.","variant":"info"},"type":"callout"}]},{"id":"understanding-problem-space","title":"Understanding the Problem Space","content":[{"data":{"content":"Before diving into heap-based solutions, let's precisely define the problem and understand why naive approaches fall short.\n\n**The K-th Largest Element Problem:**\nGiven an unsorted array of n elements, find the element that would be at position k if the array were sorted in descending order. Equivalently, this is the element larger than exactly (n - k) other elements.\n\n**The K-th Smallest Element Problem:**\nSymmetrically, find the element at position k if sorted in ascending order—larger than exactly (k - 1) elements.\n\n**Example:**\nGiven array `[3, 2, 1, 5, 6, 4]` and k = 2:\n- The 2nd largest is `5` (only `6` is larger)\n- The 2nd smallest is `2` (only `1` is smaller)"},"type":"text"},{"data":{"icon":"Info","title":"1-Indexed vs 0-Indexed","content":"Different problems use different conventions. The '1st largest' typically means the maximum, while in 0-indexed terms, it would be the element at index 0 after sorting descending. Always clarify this in interviews. Throughout this page, we use 1-indexed k (k=1 means the extreme element).","variant":"note"},"type":"callout"},{"data":{"content":"**Why This Problem Matters:**\n\nThe k-th element problem isn't just an academic exercise—it appears constantly in real systems:\n\n1. **Percentile Calculations**: Finding the 95th percentile response time\n2. **Outlier Detection**: Identifying the k most extreme anomalies\n3. **Selection Algorithms**: Choosing top-k candidates from a pool\n4. **Database Queries**: `SELECT ... ORDER BY ... LIMIT k`\n5. **Statistical Analysis**: Finding median, quartiles, deciles\n6. **Resource Allocation**: Distributing resources to top-k performers"},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"naive-approaches","title":"Naive Approaches and Their Costs","content":[{"data":{"content":"Let's systematically analyze the obvious approaches before understanding why heaps offer a superior solution."},"type":"text"},{"data":{"items":["**Algorithm**: Sort the entire array, then return the element at index k-1 (for k-th smallest) or n-k (for k-th largest)","**Time Complexity**: O(n log n) — dominated by sorting","**Space Complexity**: O(1) to O(n) depending on sorting algorithm","**Verdict**: Works but wasteful—we sorted n elements to find just one. The sorting does far more work than necessary."],"title":{"icon":"AlertCircle","text":"Approach 1: Sort and Index","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Algorithm**: Find and remove the maximum k times; the k-th removal is the answer","**Time Complexity**: O(k × n) — each extraction scans all remaining elements","**Space Complexity**: O(1) if modifying in place, O(n) otherwise","**Verdict**: Acceptable when k is tiny (k=1 or k=2), but becomes O(n²) when k is proportional to n (e.g., finding median)"],"title":{"icon":"AlertCircle","text":"Approach 2: Repeated Maximum/Minimum Extraction","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"items":["**Algorithm**: Build a max-heap from all n elements, then extract-max k times","**Time Complexity**: O(n) for heapify + O(k log n) for extractions = O(n + k log n)","**Space Complexity**: O(n) for the heap","**Verdict**: Better! But we're storing all n elements when we only care about k of them. Can we do better on space?"],"title":{"icon":"AlertCircle","text":"Approach 3: Full Heap Construction","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"Lightbulb","title":"The Key Insight","content":"The breakthrough comes from realizing we don't need to track all n elements—we only need to maintain the 'boundary' at position k. A heap of size k is sufficient to solve this problem, dramatically reducing space and enabling streaming solutions.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"counterintuitive-heap-solution","title":"The Counterintuitive Heap Solution","content":[{"data":{"content":"Here's where heap-based solutions become genuinely elegant—and initially confusing. The optimal approach uses what seems like the *wrong* heap type:\n\n**To find the k-th LARGEST, use a MIN-heap of size k.**\n**To find the k-th SMALLEST, use a MAX-heap of size k.**\n\nThis counterintuitive choice is the key insight that separates those who understand heaps from those who merely know them."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Why the 'Wrong' Heap?","content":"This seems backward at first. If we want the k-th largest, shouldn't we use a max-heap? The crucial realization: we're maintaining the k largest elements seen so far, and we need quick access to the SMALLEST of those k—that's the boundary element that might be replaced.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Algorithm for K-th Largest (using Min-Heap of size k):**\n\n1. **Initialize**: Create an empty min-heap\n2. **Process first k elements**: Insert each into the heap\n3. **Process remaining (n-k) elements**: For each element:\n - If element > heap.peek() (heap's minimum):\n - Remove the minimum\n - Insert the new element\n - Otherwise, ignore it (it's not in the top k)\n4. **Result**: heap.peek() is the k-th largest\n\n**Why This Works:**\nAt any point, the heap contains exactly the k largest elements seen so far. The heap's minimum is the smallest of these k—which is, by definition, the k-th largest overall. Elements smaller than this minimum can never be in the top k, so we ignore them."},"type":"text"},{"data":{"fileName":"kth-largest-element","languages":[{"code":"$69","label":"Python","value":"python"},{"code":"$6a","label":"Java","value":"java"},{"code":"$6b","label":"TypeScript","value":"typescript"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"visual-walkthrough","title":"Visual Walkthrough: The Heap in Action","content":[{"data":{"content":"Let's trace through the algorithm step by step to build intuition for why the min-heap approach works."},"type":"text"},{"data":{"rows":[["1","3","Push (heap size < k)","[3]","Building initial k-element heap"],["2","2","Push (heap size < k)","[2, 3]","Heap now has k=2 elements"],["3","1","Skip (1 < heap min 2)","[2, 3]","1 can never be in top 2"],["4","5","Replace (5 > 2)","[3, 5]","5 kicks out 2, joins top 2"],["5","6","Replace (6 > 3)","[5, 6]","6 kicks out 3, joins top 2"],["6","4","Skip (4 < heap min 5)","[5, 6]","4 can never be in top 2"]],"caption":"Finding 2nd Largest in [3, 2, 1, 5, 6, 4]","headers":["Step","Element","Action","Heap State","Reasoning"]},"type":"table"},{"data":{"content":"**Final Result**: The heap contains `[5, 6]`—the two largest elements. The heap minimum `5` is the 2nd largest.\n\n**Key Observations:**\n\n1. **The heap acts as a 'sliding window' of top-k elements**: At any moment, it holds exactly the k largest elements seen so far.\n\n2. **The min-heap root is the 'entry barrier'**: Any new element must beat this minimum to join the top k.\n\n3. **Rejected elements are permanently excluded**: If an element is smaller than the current heap minimum, it cannot possibly be in the final top k.\n\n4. **Efficiency comes from rejection**: We only perform O(log k) heap operations when an element actually enters the heap. Elements that are rejected require only O(1) comparison."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Bouncer Analogy","content":"Think of the min-heap as a VIP club with exactly k spots. The heap minimum is the 'bouncer' at the door. A new arrival must be more impressive than the least impressive current VIP to get in—and if they do, the former least-impressive VIP gets kicked out.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"kth-smallest","title":"K-th Smallest: The Symmetric Case","content":[{"data":{"content":"Finding the k-th smallest uses the exact same logic, but with the heap polarity reversed:\n\n**To find the k-th SMALLEST, use a MAX-heap of size k.**\n\nThe max-heap now maintains the k *smallest* elements seen so far, with quick access to the largest of them (the k-th smallest overall)."},"type":"text"},{"data":{"fileName":"kth-smallest-element","languages":[{"code":"$6c","label":"Python","value":"python"},{"code":"import java.util.PriorityQueue;\nimport java.util.Collections;\n\npublic class KthSmallestElement {\n /**\n * Find the k-th smallest element using a max-heap of size k.\n * \n * Time Complexity: O(n log k)\n * Space Complexity: O(k)\n */\n public static int findKthSmallest(int[] nums, int k) {\n // PriorityQueue with reverse order = max-heap\n PriorityQueue maxHeap = new PriorityQueue<>(\n Collections.reverseOrder()\n );\n \n for (int num : nums) {\n if (maxHeap.size() < k) {\n maxHeap.offer(num);\n } else if (num < maxHeap.peek()) {\n maxHeap.poll();\n maxHeap.offer(num);\n }\n }\n \n return maxHeap.peek();\n }\n \n public static void main(String[] args) {\n int[] nums = {3, 2, 1, 5, 6, 4};\n int k = 2;\n int result = findKthSmallest(nums, k);\n System.out.println(\"The \" + k + \"th smallest: \" + result); // 2\n }\n}","label":"Java","value":"java"}]},"type":"code"},{"data":{"rows":[["K-th Largest","Min-Heap","k","Heap root (minimum)"],["K-th Smallest","Max-Heap","k","Heap root (maximum)"],["All Top K Largest","Min-Heap","k","Entire heap contents"],["All Top K Smallest","Max-Heap","k","Entire heap contents"]],"caption":"Summary: Which Heap for Which Problem","headers":["Finding","Use This Heap","Heap Size","Answer Location"]},"type":"table"}],"titleType":"number","titleNumber":5},{"id":"complexity-analysis","title":"Complexity Analysis Deep Dive","content":[{"data":{"content":"Understanding the complexity tradeoffs is crucial for knowing when the heap approach is optimal."},"type":"text"},{"data":{"rows":[["Sort + Index","O(n log n)","Multiple queries on same data"],["Heap (size k)","O(n log k)","k << n (small k)"],["Heap (size n-k)","O(n log(n-k))","k close to n"],["QuickSelect","O(n) average, O(n²) worst","One-time query, average case OK"],["Introselect","O(n) worst case","Guaranteed linear time needed"]],"caption":"Time Complexity Comparison","headers":["Approach","Time Complexity","Best When"]},"type":"table"},{"data":{"content":"**Detailed Analysis of the Heap Approach:**\n\n**Time Complexity: O(n log k)**\n\n- We iterate through all n elements: O(n)\n- For each element, we potentially do one heap operation: O(log k)\n- In the worst case (sorted ascending array, finding k-th largest), every element after the first k causes a replacement\n- Therefore: O(n log k)\n\n**When k is small (k << n):**\nlog k is nearly constant. If k = 10 and n = 1,000,000:\n- Sorting: O(n log n) ≈ 20 million operations\n- Heap: O(n log k) ≈ 3.3 million operations\n- **6x improvement!**\n\n**When k is close to n:**\nThe heap approach is less advantageous. Consider finding the (n-1)-th largest (the 2nd smallest). Using a min-heap of size (n-1) is essentially O(n log n).\n\n**Optimization**: If k > n/2, find the (n-k+1)-th smallest instead using the opposite heap type. This ensures heap size ≤ n/2."},"type":"text"},{"data":{"fileName":"optimized-kth-element","languages":[{"code":"$6d","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Space Complexity: O(k)**\n\nThe heap stores exactly k elements. This is a significant advantage over sorting (O(1) to O(n) depending on algorithm) when k is small.\n\nMore importantly, the **O(k) space enables streaming**: we can process elements as they arrive without storing the entire dataset. This is impossible with sorting-based approaches."},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"streaming-data","title":"Streaming Data and Real-Time Queries","content":[{"data":{"content":"One of the most powerful applications of the heap-based k-th element algorithm is handling **streaming data**—where elements arrive continuously and we need to answer queries at any moment.\n\nThe heap approach naturally extends to this scenario:"},"type":"text"},{"data":{"items":["**Constant space**: O(k) regardless of stream length","**O(log k) per element**: Each new arrival is processed in logarithmic time","**Instant queries**: The k-th element is always at the heap root—O(1) access","**No re-processing**: We never need to revisit old elements"],"title":{"icon":"Zap","text":"Streaming Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"fileName":"streaming-kth-largest","languages":[{"code":"$6e","label":"Python","value":"python"},{"code":"$6f","label":"Java","value":"java"}]},"type":"code"},{"data":{"icon":"CheckCircle","title":"LeetCode Problem: 703. Kth Largest Element in a Stream","content":"This exact pattern is tested in LeetCode problem 703. The streaming k-th largest class is a direct solution. Understanding this pattern unlocks an entire category of real-time monitoring problems.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"quickselect-alternative","title":"Alternative Approach: QuickSelect","content":[{"data":{"content":"While heaps provide an elegant O(n log k) solution, there exists a fundamentally different approach that achieves O(n) *average* time: **QuickSelect**.\n\nQuickSelect is the selection analog of QuickSort, using the same partitioning strategy but only recursing into the half containing our target rank."},"type":"text"},{"data":{"left":[{"data":{"items":["O(n) average time complexity","O(1) extra space (in-place)","Theoretically optimal for single query"],"title":{"icon":"CheckCircle","text":"QuickSelect Advantages","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["O(n²) worst case (bad pivot selection)","Modifies the input array","Cannot handle streaming data"],"title":{"icon":"XCircle","text":"QuickSelect Disadvantages","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"fileName":"quickselect","languages":[{"code":"$70","label":"Python","value":"python"}]},"type":"code"},{"data":{"rows":[["Single query, can modify array","QuickSelect","O(n) average beats O(n log k)"],["Streaming data","Heap","QuickSelect can't handle streams"],["Multiple queries, same k","Heap","Heap state persists across additions"],["Multiple different k queries","Sort once","O(n log n) + O(1) per query"],["Small k, large n","Heap","O(n log k) ≈ O(n) when k is tiny"],["Guaranteed worst-case bound","Introselect or Heap","QuickSelect can degrade to O(n²)"]],"caption":"When to Use Each Approach","headers":["Scenario","Best Choice","Reason"]},"type":"table"}],"titleType":"number","titleNumber":8},{"id":"problem-variations","title":"Common Problem Variations","content":[{"data":{"content":"The k-th element pattern appears in many disguised forms. Recognizing these variations is key to interview success."},"type":"text"},{"data":{"items":["**Top K Frequent Elements**: Use a min-heap of size k, but keyed by frequency. The heap maintains k elements with highest frequencies.","**K Closest Points to Origin**: Use a max-heap of size k with distance as key. The heap maintains k points with smallest distances.","**K Smallest in Sorted Matrix**: Use a min-heap with matrix elements. Similar but exploits sorted structure for efficiency.","**Sliding Window Maximum**: Related pattern using a different structure (monotonic deque), but similar 'tracking extremes' intuition.","**K-th Smallest in BST**: Can use in-order traversal (O(n)) or augmented BST (O(log n) with tree modification).","**K-th Smallest Sum of Pairs**: Use heap to explore sum space incrementally."],"title":{"icon":"Target","text":"Pattern Variations","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"icon":"AlertCircle","title":"The Transformation Skill","content":"The key skill is recognizing that a problem can be *reduced* to finding a k-th element. 'Top K by some metric' → 'K-th largest by that metric'. 'K closest to target' → 'K smallest by distance'. Train yourself to see through the problem's disguise.","variant":"warning"},"type":"callout"},{"data":{"fileName":"top-k-frequent","languages":[{"code":"$71","label":"Python","value":"python"}]},"type":"code"}],"titleType":"number","titleNumber":9},{"id":"summary","title":"Summary: The K-th Element Pattern","content":[{"data":{"content":"We've completed a deep dive into one of the most important heap patterns. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Use the 'opposite' heap**: Min-heap for k-th largest, max-heap for k-th smallest. This counterintuitive choice is the core insight.","**Heap size = k**: Maintain exactly k elements, representing the top k by your desired metric. The heap root is the boundary.","**O(n log k) time, O(k) space**: Superior to sorting when k << n, and enables streaming which sorting cannot.","**Streaming-friendly**: The heap approach naturally handles continuous data arrival with O(log k) updates and O(1) queries.","**Pattern recognition**: 'Top K by X' reduces to 'K-th largest by X'. Train yourself to spot this transformation.","**Know your alternatives**: QuickSelect offers O(n) average time for single queries on static data with in-place modification."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nThe k-th element pattern is just the beginning. In the next page, we'll explore another powerful heap application: **merging k sorted lists**. This pattern builds on the same heap intuition but applies it to a different problem structure—maintaining the frontier of k separate sequences."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Pattern Mastered","content":"You now understand the k-th element pattern deeply—not just the algorithm, but the underlying reasoning. When you encounter variations in interviews or production code, you'll recognize the pattern and apply the technique with confidence.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":10}],"isLocked":false},{"id":"seed_69b9abb105a5fe13a8035d6288c7ca2a","title":"Merge K Sorted Lists","order":1,"content":null,"isLocked":true},{"id":"seed_09751837d0045698ca1ab21bcefb15b6","title":"Median Maintenance","order":2,"content":null,"isLocked":true},{"id":"seed_dcff8290bb52391e7b1fdfba024744ae","title":"Task Scheduling with Priorities","order":3,"content":null,"isLocked":true},{"id":"seed_a099f0797a03cc47769669e02c26875e","title":"Event-Driven Simulation","order":4,"content":null,"isLocked":true}]}}