Kth Largest, Median and Order Statistics in Interviews

Use a min-heap of size k when the data arrives as a stream or you must not modify the input array: it costs O(n log k) time and O(k) extra memory. Use Quickselect for a static array you are allowed to rearrange: it runs in linear time on average and partitions in place, so it is the one that needs less extra memory, not more. Stop trying to sort the entire array for every order statistic problem, as that is an unnecessary performance penalty that interviewers notice immediately.

Quickselect versus Heaps

When you need the kth largest element in an array like [3, 2, 1, 5, 6, 4] where k is 2, sorting takes O(n log n). A min-heap of size k keeps the largest elements at the top, resulting in O(n log k) time. This is efficient if k is small. However, Quickselect uses the partition logic from Quicksort to narrow down the search space. By picking a pivot and discarding the half that does not contain the kth index, you reach an average time complexity of O(n).

Consider the array [7, 10, 4, 3, 20, 15] and k equals 3. If you pick 10 as the pivot, you partition the array into [7, 4, 3] and [20, 15]. Since the right side has two elements, the 3rd largest must be in the left side. You repeat the process on [7, 4, 3] until the index aligns. This avoids the overhead of maintaining a heap structure when the full array is already in memory.

Median of two sorted arrays

Finding the median of two sorted arrays, such as A = [1, 3] and B = [2], requires a binary search on the partition point. You are not looking for the median directly; you are looking for a cut that splits both arrays such that the left side contains half the total elements. If you have n elements in A and m elements in B, you perform a binary search on the smaller array to find a partition i such that A[i-1] <= B[j] and B[j-1] <= A[i]. This runs in O(log(min(n, m))). Do not merge the arrays into a new one, as that forces O(n + m) space and time.

Running median with two heaps

When the input is a stream of numbers, you cannot use Quickselect because the array is not static. Use two heaps: a max-heap for the lower half of the numbers and a min-heap for the upper half. If you receive 5, 15, 1, 3, you insert 5 into the max-heap, then 15 into the min-heap. Balance the heaps so their sizes differ by at most one. The median is either the root of the larger heap or the average of both roots. This keeps the insertion and median retrieval at O(log n) per element.

Rule of thumb for interviews

• Static array and need kth element: Use Quickselect for O(n) average time.
• Streaming data: Use two heaps to maintain the median in O(log n).
• Two sorted arrays: Use binary search on the partition to hit O(log(min(n, m))).
• Memory is extremely limited: Use a heap to avoid modifying the input array.

DSA Tracker provides these patterns to help you recognize which structure fits the constraints of your specific problem. Practice implementing the partition function for Quickselect until you can write it without looking at a reference, as this is the most common point of failure during a whiteboard session.

Keep going with the step-by-step visualizer and practice problems.