Definition
- Min-heap of size K – maintains only the K largest elements; the root (smallest of those) is the Kth largest. O(n log K) time, O(K) space.
- QuickSelect – partitions the array around a pivot and recurses into only the side containing the target index. Average O(n) time, O(1) extra space.
- Randomized pivot – prevents worst-case O(n^2) in QuickSelect by choosing a random pivot.
- Streaming vs batch – heap works for streaming; QuickSelect needs the full array in memory.
At the National Bank of India, the risk desk sets a daily alert threshold from the Kth largest transaction amount. The heap approach keeps a shortlist of exactly K biggest amounts; whenever a bigger amount arrives, it bumps out the smallest on the shortlist. QuickSelect splits amounts into bigger and smaller piles and keeps narrowing to the pile containing the rank you want.
Understanding the Concepts
What is the problem?
Given an unsorted array and a value K, return the Kth largest element by value (not the Kth distinct). For example, in [3,2,1,5,6,4] with K=2, the answer is 5.
At the National Bank of India, the risk desk needs the Kth largest transaction to set an alert threshold.
How does the min-heap approach work?
Push each element. When the heap exceeds K, poll the smallest. After one pass, the root is the Kth largest.
package com.bank.analytics;
import java.util.PriorityQueue;
public class KthLargestHeap {
public static int findKthLargest(int[] amounts, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int amount : amounts) {
minHeap.offer(amount);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public static void main(String[] args) {
int[] transactions = {5000, 2000, 8000, 1000, 9000, 3000};
System.out.println("2nd largest: " + findKthLargest(transactions, 2));
}
}
2nd largest: 8000
How does QuickSelect work?
Reframe the problem: the Kth largest is the element at index n - K in ascending sorted order. Partition around a pivot, then recurse into the correct side.
package com.bank.analytics;
import java.util.Random;
public class KthLargestQuickSelect {
private static final Random rand = new Random();
public static int findKthLargest(int[] amounts, int k) {
int target = amounts.length - k;
return quickSelect(amounts, 0, amounts.length - 1, target);
}
private static int quickSelect(int[] arr, int lo, int hi, int target) {
if (lo == hi) return arr[lo];
int pivotIdx = lo + rand.nextInt(hi - lo + 1);
swap(arr, pivotIdx, hi);
int pivot = arr[hi];
int storeIdx = lo;
for (int i = lo; i < hi; i++) {
if (arr[i] < pivot) {
swap(arr, i, storeIdx);
storeIdx++;
}
}
swap(arr, storeIdx, hi);
if (storeIdx == target) return arr[storeIdx];
else if (target < storeIdx) return quickSelect(arr, lo, storeIdx - 1, target);
else return quickSelect(arr, storeIdx + 1, hi, target);
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
public static void main(String[] args) {
int[] transactions = {5000, 2000, 8000, 1000, 9000, 3000};
System.out.println("2nd largest: " + findKthLargest(transactions, 2));
}
}
2nd largest: 8000
How do the two approaches compare?
| Aspect | Min-Heap | QuickSelect |
|---|---|---|
| Time (average) | O(n log K) | O(n) |
| Time (worst) | O(n log K) | O(n^2) without random pivot |
| Space | O(K) | O(1) extra (in-place) |
| Mutates input | No | Yes |
| Streaming | Yes | No (needs full array) |
| Simplicity | Simple | More complex |
Why randomize the pivot in QuickSelect?
Without randomization, a sorted or nearly-sorted array causes the worst partition every time: one side gets n-1 elements and the other gets 0. This degrades to O(n^2). Randomizing the pivot makes bad partitions statistically rare.
// Without random: worst case O(n^2) on sorted input
int pivotIdx = hi; // always picks the last element
// With random: expected O(n)
int pivotIdx = lo + rand.nextInt(hi - lo + 1);
What are common mistakes?
Using a max-heap instead of a min-heap. A max-heap would need to hold all n elements and then poll K-1 times, which is O(n log n) rather than O(n log K).
// Wrong: max-heap needs all elements
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int x : arr) maxHeap.offer(x);
for (int i = 0; i < k - 1; i++) maxHeap.poll();
return maxHeap.peek(); // O(n log n)
// Correct: size-K min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int x : arr) {
minHeap.offer(x);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.peek(); // O(n log K)
What are the edge cases?
- K = 1: return the maximum element.
- K = n: return the minimum element.
- All elements equal: any element is the Kth largest.
- Array of size 1: return the single element (K must be 1).
What should a senior engineer know?
The trade-off between heap and QuickSelect is what interviewers want. State it clearly:
- Heap: simple, worst-case O(n log K), streaming-friendly, does not mutate input.
- QuickSelect: average linear, mutates input, needs full array, requires randomization.
For the Kth smallest, the same approaches apply: use a max-heap of size K, or target index K-1 in QuickSelect.
What are common interview follow-up questions?
- What if data arrives as a stream? (Use the min-heap, updated on each arrival.)
- What if K is very close to n? (The heap holds almost all elements; QuickSelect is better.)
- Can you guarantee O(n) worst case? (Use median-of-medians as the pivot selection, but it is rarely practical.)
Visual Overview
Transactions: [5000, 2000, 8000, 1000, 9000, 3000] K = 2
Min-Heap (size K=2):
offer 5000 -> [5000]
offer 2000 -> [2000, 5000]
offer 8000 -> size 3 > 2, poll 2000 -> [5000, 8000]
offer 1000 -> size 3 > 2, poll 1000 -> [5000, 8000]
offer 9000 -> size 3 > 2, poll 5000 -> [8000, 9000]
offer 3000 -> size 3 > 2, poll 3000 -> [8000, 9000]
Root = 8000 = 2nd largest ✓
┌──────────────────────────────────────────────┐ │ Kth Largest: Two Approaches │ ├──────────────────────────────────────────────┤ │ │ │ Approach A: Size-K Min-Heap │ │ ┌──────────────────────────────┐ │ │ │ for each element: │ │ │ │ heap.offer(element) │ │ │ │ if heap.size > K: poll │ │ │ │ return heap.peek() │ │ │ └──────────────────────────────┘ │ │ │ │ Approach B: QuickSelect │ │ ┌──────────────────────────────┐ │ │ │ target = n - K │ │ │ │ partition around random pivot │ │ │ │ recurse into correct side │ │ │ │ return element at target │ │ │ └──────────────────────────────┘ │ └──────────────────────────────────────────────┘
Key Takeaway
Finding the Kth largest element has two strong solutions. The size-K min-heap keeps only the K largest elements: push each element, poll when the heap exceeds K, and the root is the Kth largest. This runs in O(n log K) and is ideal for streaming data.
QuickSelect reframes the problem as finding the element at index n-K in ascending order. Partition around a random pivot, discard the side that cannot contain the target, and recurse into the correct side. Average time is O(n), but a bad pivot sequence degrades to O(n^2), so always randomize.
The trade-off is clear: heap is simple, worst-case predictable, streaming-friendly, and non-destructive. QuickSelect is faster on average but mutates the array and needs the full data in memory.
At the National Bank of India, the risk desk set a daily alert threshold from the Kth largest transaction. Amounts streamed in all day, so Rajesh used the min-heap, keeping only K values at any moment. QuickSelect was the option for batch recomputation over a finished day's data.
Remember one sentence: a size-K min-heap keeps the K largest elements, and its root is the Kth largest after one pass.
---