Finding Medians and Percentiles in Data Streams

Median and percentile problems are fundamental in statistics and real-time data processing scenarios where you need to efficiently find central values or rank-based thresholds in dynamic datasets.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input array? Will it be small (< 1000), medium (1000-100K), or large (> 100K)?
2. Are duplicates allowed in the input array? If so, how should they be handled in median calculation?
3. Should I return the median as a double or can it be an integer if the result is a whole number?
4. Can I mutate the input array, or must I preserve it?
5. What is the target time complexity for follow-up questions? Should I aim for O(n) or O(n log n)?

Restatement of the pattern: This pattern involves finding the median (or other percentiles) of a dataset, which is a fundamental statistical operation that requires identifying the middle element(s) in a sorted sequence. The median represents the value that separates the higher half from the lower half of the data.

Signal words and constraint shape: Key indicators include phrases like "find median," "middle element," "kth smallest/largest," "percentile calculation," or "find the element that would be at position k in a sorted array." The constraint shape typically involves arrays or streams where we need to efficiently locate elements relative to their sorted order without fully sorting the data.

Assumptions made:

• The input is a collection of comparable elements (numbers)
• For odd-length arrays, the median is the middle element; for even-length arrays, it's the average of the two middle elements
• The problem can be solved with a single pass or multiple passes through the data, depending on constraints

Scenario suitability: This pattern is best suited for static scenarios where the entire dataset is available. For streaming data, we'd likely use a different approach such as maintaining a sliding window or using reservoir sampling techniques. The pattern works well in batch processing contexts where we can afford to analyze the complete dataset once.

The core insight is that we don't need to fully sort the array to find the median—we can use partitioning techniques or heap-based approaches to efficiently locate the target element(s) in O(n) expected time.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Median", "middle element", "kth smallest/largest", "percentile", "ranking"
• "Find the median of a stream" or "running median"
• "Online algorithm" or "streaming data" where elements arrive one at a time
• "Find the kth element in sorted order" or "find the element that would be at position k if array were sorted"
• Constraints like "find median in O(1) time" or "maintain median as elements are added"

Why this pattern fits better than the most common alternatives:

• Sorting approach: O(n log n) for each query, too slow for streaming scenarios
• Binary search with sorting: Still requires maintaining sorted order, O(n) insertion time
• Simple heap approach: Can't efficiently handle streaming updates with O(1) median access
• The key insight is that we need to maintain a data structure that allows us to quickly access the middle element(s) of a dynamic collection, which requires balancing two heaps or similar structure

Conditions where a variation or related pattern applies instead:

• If we only need to find one specific percentile (like 90th), we can use bucketing or quantile estimation instead of maintaining full median structure
• For static arrays where we don't need to support insertions, sorting + binary search is sufficient and simpler
• When we only care about approximate median with bounded error, reservoir sampling or quantile sketches work better

The core insight that makes this pattern work: We can maintain the median by keeping track of elements in two partitions - one containing all elements ≤ median and another containing all elements ≥ median. By ensuring these partitions are balanced, we can always access the median in O(1) time by looking at the top of each partition.

This pattern is particularly suited for streaming scenarios where we need to maintain a running median as new elements arrive, since it allows us to efficiently rebalance the partitions when new elements are added.

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I sort the entire array and pick the middle element. But that's O(n log n) because sorting dominates the complexity, and we're not leveraging any properties of finding just the median. Let me think about how to optimize this...

I notice that if I maintain a way to quickly access the median, I can reduce it to O(n log n) by using a data structure like a heap or balanced BST. But actually, there's an even better approach - I can use the QuickSelect algorithm which is based on quicksort's partitioning strategy, and it gives us O(n) average time complexity.

Let me think about what invariants I need to maintain. For finding the median, I want to partition the array so that elements smaller than my target are on one side and larger elements are on the other. The key insight is that I don't need to sort everything - I just need to find the right partition point.

If I'm looking for the median in an array of size n, I want to find the element at position n/2 (or average of positions n/2 and n/2-1 for even-length arrays). I can use a partitioning approach similar to quicksort, but instead of recursively sorting both sides, I only recurse on the side that contains my target position.

This approach maintains the invariant that all elements to the left of my partition are less than or equal to the median, and all elements to the right are greater than or equal to the median. The algorithm terminates when I find the exact position where the median should be."

Brute-force approach and why it is not ideal: The most straightforward approach is to sort the entire array and return the middle element(s). This has O(n log n) time complexity due to sorting, which is inefficient for the median problem since we don't need full ordering.

Improved approach and the key optimization: The key optimization is using QuickSelect algorithm, which partitions the array around a pivot and only recurses on the relevant partition containing the target element. This reduces average time complexity from O(n log n) to O(n).

Final approach with step-by-step reasoning:

1. Use partitioning similar to quicksort to find the median position
2. For odd-length arrays, find element at index n/2
3. For even-length arrays, find elements at indices n/2-1 and n/2, then average them
4. Only recurse on the partition containing the target position to avoid full sorting
5. Maintain the invariant that elements to left are ≤ median, elements to right are ≥ median

Important invariants that must hold:

• Elements to the left of partition point are ≤ median value
• Elements to the right of partition point are ≥ median value
• When partition point equals target index, we've found our median
• The algorithm maintains relative ordering within partitions but not global order

4. Data Structure Choice

For median finding problems, the primary data structures needed are:

1. Two Heaps (Max-heap and Min-heap)

• Why needed: The most efficient approach for maintaining median in streaming scenarios uses a max-heap for the lower half and a min-heap for the upper half of elements
• Time/Spatial impact: O(n) space for storing all elements, O(log n) time for insertions/deletions
• Key benefit: Allows O(1) access to median and O(log n) updates

2. Balanced Binary Search Tree (Optional)

• Why needed: Alternative approach that maintains elements in sorted order for direct median access
• Time/Spatial impact: O(n) space, O(log n) for insertions/deletions and median access
• Trade-off: More complex to implement than heaps, but provides direct ordering

3. Array with Sorting (For static scenarios)

• Why needed: When the entire dataset is available upfront, sorting once and accessing by index is sufficient
• Time/Spatial impact: O(n log n) for sorting, O(1) space for additional storage beyond input
• Trade-off: Not suitable for streaming or frequent updates

Helper structures:

• PriorityQueue wrappers: Custom implementations to maintain heap invariants
• Index tracking variables: For maintaining median position in sorted arrays

The two-heap approach is chosen because it provides optimal time complexity for both streaming and static scenarios, with clean separation of concerns between the lower and upper halves of the data distribution.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: nums = [3, 1, 4, 1, 5, 9, 2, 6]

Step 1: Initialize data structures

• maxHeap (max priority queue): stores smaller half, root is largest in that half
• minHeap (min priority queue): stores larger half, root is smallest in that half
• Both heaps are empty initially

Step 2: Process 3 (first element)

• Add to maxHeap: maxHeap = [3]
• Balance heaps: maxHeap = [3], minHeap = []
• Since heaps are balanced, median is maxHeap.peek() = 3

Step 3: Process 1

• Add to maxHeap: maxHeap = [3, 1]
• Balance heaps: maxHeap = [1], minHeap = [3]
• Since heaps are balanced, median is maxHeap.peek() = 1

Step 4: Process 4

• Add to minHeap: maxHeap = [1], minHeap = [3, 4]
• Balance heaps: maxHeap = [1, 3], minHeap = [4]
• Since heaps are balanced, median is maxHeap.peek() = 3

Step 5: Process 1 (again)

• Add to maxHeap: maxHeap = [3, 1, 1]
• Balance heaps: maxHeap = [1, 1], minHeap = [3, 4]
• Since heaps are balanced, median is maxHeap.peek() = 1

Step 6: Process 5

• Add to minHeap: maxHeap = [1, 1], minHeap = [3, 4, 5]
• Balance heaps: maxHeap = [1, 1, 3], minHeap = [4, 5]
• Since heaps are balanced, median is maxHeap.peek() = 3

Step 7: Process 9

• Add to minHeap: maxHeap = [1, 1, 3], minHeap = [4, 5, 9]
• Balance heaps: maxHeap = [1, 1, 3, 4], minHeap = [5, 9]
• Since heaps are unbalanced (size difference of 2), move 4 to minHeap
• Final state: maxHeap = [1, 1, 3], minHeap = [4, 5, 9]
• Since heaps are balanced, median is maxHeap.peek() = 3

Step 8: Process 2

• Add to maxHeap: maxHeap = [1, 1, 3, 2]
• Balance heaps: maxHeap = [1, 1, 2], minHeap = [3, 4, 5, 9]
• Since heaps are balanced, median is maxHeap.peek() = 2

Step 9: Process 6

• Add to minHeap: maxHeap = [1, 1, 2], minHeap = [3, 4, 5, 9, 6]
• Balance heaps: maxHeap = [1, 1, 2, 3], minHeap = [4, 5, 6, 9]
• Since heaps are balanced, median is maxHeap.peek() = 3

Key Invariants Maintained:

1. All elements in maxHeap ≤ all elements in minHeap
2. Size difference between heaps is at most 1
3. MaxHeap always contains the median or one element before median

Edge Case Handling:

• When input is empty, return 0.0 (as specified in problem)
• When single element, median is that element
• When even number of elements, median is average of two middle elements (max of left half and min of right half)
• The balancing ensures that the median is always accessible from maxHeap root

This approach correctly maintains the median by keeping track of just the relevant elements rather than sorting the entire array each time.

6. Java Solution

import java.util.*;

public class MedianFinder {
    // Max heap for the smaller half of numbers
    private PriorityQueue<Integer> maxHeap;
    // Min heap for the larger half of numbers
    private PriorityQueue<Integer> minHeap;
    
    public MedianFinder() {
        // Max heap: custom comparator to make it max-oriented
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // Min heap: default behavior
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // Add to max heap first (smaller half)
        maxHeap.offer(num);
        
        // Balance: move the largest of smaller half to larger half
        if (!maxHeap.isEmpty() && !minHeap.isEmpty() && 
            maxHeap.peek() > minHeap.peek()) {
            int maxOfSmall = maxHeap.poll();
            minHeap.offer(maxOfSmall);
        }
        
        // Rebalance heaps to maintain size difference at most 1
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size() + 1) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            // Even number of elements: average of both heaps' tops
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else if (maxHeap.size() > minHeap.size()) {
            // Odd number of elements: max heap has the extra element
            return (double) maxHeap.peek();
        } else {
            // Odd number of elements: min heap has the extra element
            return (double) minHeap.peek();
        }
    }
}

This implementation uses two heaps to efficiently maintain and retrieve the median of a dynamic data stream. The max heap stores the smaller half of numbers, and the min heap stores the larger half. By maintaining size balance between the heaps, we ensure O(1) median retrieval and O(log n) insertion time.

7. Complexity Analysis

Time Complexity: O(n log n)

The time complexity comes from the sorting operation, which is the dominant factor in our solution. We perform a single pass through the input array to build our sorted list, and then we sort it. The sorting operation takes O(n log n) time where n is the number of elements in the input array.

The subsequent median calculation is O(1) since we're just accessing elements by index, and the binary search operations for maintaining the sorted order are O(log n) per insertion, but since we're doing this for each element in the array, and we're not using a more sophisticated data structure like heaps or balanced trees for maintaining order, the overall complexity remains dominated by sorting.

Space Complexity: O(n)

We use additional space proportional to the input size:

• sortedList stores all n elements from the input array, requiring O(n) space
• The ArrayList used for storing the result also requires O(k) space where k is the number of medians computed (which in our case equals n, since we compute a median for each position)

The space complexity is linear with respect to the input size, making it efficient in terms of space usage for this problem.

Why these bounds are correct:

The O(n log n) time bound is tight because:

1. Sorting is a fundamental operation that cannot be done better than O(n log n) in the comparison model
2. Our approach requires sorting to properly compute running medians, and we cannot avoid this step

The O(n) space bound is tight because:

1. We must store all input elements to compute the running medians
2. No compression or approximation is used that would reduce space requirements

Optimality:

This solution is near-optimal for the given constraints. If we were to use a more sophisticated approach like maintaining two heaps (max-heap for smaller half, min-heap for larger half), we could achieve O(n log n) time complexity with better constants, but the sorting-based approach is simpler to implement and understand. The current solution is optimal in terms of algorithmic complexity for the problem as stated.

The sorting approach is particularly appropriate when we need to compute medians for all positions in the array, as opposed to just finding one median or when we don't have streaming data where maintaining dynamic order would be more efficient.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should handle gracefully, typically returning 0.0 or throwing an appropriate exception
• Single element: Should return that element as the median
• Two elements: Should return average of both elements

Duplicate Values and Repeated States

• All duplicates: The algorithm must correctly handle arrays where all elements are identical
• Duplicate medians: When duplicates exist, ensure the correct median position is identified (especially in even-length arrays)
• Edge case with duplicates: Arrays like [1, 1, 2, 2] where the median calculation depends on proper indexing

Boundary Conditions

• Array size at limits: Very large arrays (close to Integer.MAX_VALUE) may cause overflow in indexing calculations
• Integer overflow: When calculating midpoints or indices, ensure proper handling of large numbers
• Index bounds: Ensure array access never goes out of bounds, particularly when using binary search or two-pointer approaches

Common Implementation Mistakes

• Incorrect median calculation: For even-length arrays, failing to properly average the two middle elements or using wrong indices (e.g., arr[n/2] instead of arr[n/2-1] and arr[n/2])
• Off-by-one errors: Using <= instead of < in loop conditions or incorrectly handling the middle element in odd-length arrays
• Wrong data structure usage: Using ArrayList instead of int[] when the problem guarantees sorted input, or not maintaining proper ordering in heap-based approaches
• Not handling floating-point precision: When returning median as double, ensure proper casting and avoid integer division errors

Memory and Performance Pitfalls

• Unnecessary array copying: Creating new arrays when the original can be used directly (especially in streaming scenarios)
• Inefficient data structure operations: Using O(n) operations inside loops when O(1) alternatives exist
• Not leveraging input constraints: Failing to use the fact that input is sorted or that elements are in a known range

9. Alternative Approaches

There are several alternative approaches to solving median-related problems, each with different trade-offs:

1. Sorting-based approach: Sort the entire array and return the middle element(s). This is O(n log n) time and O(1) space if we don't count the sorting overhead. This approach is simple to implement but inefficient for large datasets where we only need the median.

2. Quickselect-based approach: Use the quickselect algorithm to find the kth smallest element in O(n) average time. This is more efficient than sorting but has worst-case O(n²) behavior and requires careful pivot selection to maintain good average performance.

3. Min-heap + Max-heap approach: Maintain two heaps - a max-heap for the smaller half and a min-heap for the larger half. This allows O(log n) insertion and O(1) median retrieval, making it ideal for streaming data scenarios where elements arrive one at a time.

4. Frequency counting approach: For problems with limited value ranges, we can use frequency arrays or hash maps to count occurrences and find the median by accumulating counts. This is O(n + k) where k is the range of values, but only practical when k is small.

The chosen solution using two heaps is preferred for streaming scenarios because it maintains the median in real-time with efficient updates, while other approaches are better suited for batch processing or when memory constraints are more severe. The heap-based approach provides the best balance of time complexity and adaptability to dynamic data streams.

// Alternative: Min-heap + Max-heap approach for streaming median
class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // stores smaller half
    private PriorityQueue<Integer> minHeap; // stores larger half
    
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }
        
        // Rebalance heaps
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size() + 1) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        } else {
            return minHeap.peek();
        }
    }
}

10. Test Cases

public class MedianFinderTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic odd-length array
        int[] nums1 = {3, 1, 4, 1, 5};
        // Expected median: 3 (sorted: [1,1,3,4,5])
        
        // Test case 2: Basic even-length array
        int[] nums2 = {2, 4, 6, 8};
        // Expected median: 5 (sorted: [2,4,6,8], average of 4 and 6)
        
        // Test case 3: Single element
        int[] nums3 = {42};
        // Expected median: 42
        
        // Test case 4: Two elements
        int[] nums4 = {10, 20};
        // Expected median: 15.0 (average of 10 and 20)
        
        // Test case 5: All same elements
        int[] nums5 = {5, 5, 5, 5};
        // Expected median: 5.0
        
        // Test case 6: Negative numbers
        int[] nums6 = {-1, -2, -3, -4};
        // Expected median: -2.5 (average of -2 and -3)
        
        // Test case 7: Mixed positive and negative
        int[] nums7 = {1, -1, 0};
        // Expected median: 0.0
        
        // Test case 8: Large numbers
        int[] nums8 = {1000000, 2000000, 3000000};
        // Expected median: 2000000.0
        
        // Test case 9: Empty array (edge case)
        int[] nums9 = {};
        // Expected: throw exception or handle gracefully
        
        // Test case 10: Large array with duplicates
        int[] nums10 = {1, 2, 2, 3, 3, 3, 4, 4, 5};
        // Expected median: 3.0 (sorted: [1,2,2,3,3,3,4,4,5])
    }
}

Representative Test Cases:

Sample 1 - Basic odd-length array:

• Input: {3, 1, 4, 1, 5}
• Expected: 3.0 (sorted array: [1,1,3,4,5], middle element)
• Purpose: Validates basic median calculation for odd-length arrays

Sample 2 - Basic even-length array:

• Input: {2, 4, 6, 8}
• Expected: 5.0 (sorted array: [2,4,6,8], average of middle elements)
• Purpose: Validates median calculation for even-length arrays

Tricky Case - Mixed positive and negative numbers:

• Input: {1, -1, 0}
• Expected: 0.0 (sorted array: [-1,0,1], middle element)
• Purpose: Tests handling of negative numbers and zero

Boundary Case - Empty array:

• Input: {}
• Expected: Exception or special handling
• Purpose: Validates proper error handling for edge case

The test cases cover all major scenarios including odd/even length arrays, single elements, duplicates, negative numbers, and boundary conditions to ensure robust implementation.

11. Final Summary

The core idea is to maintain two heaps to efficiently track and retrieve the median of a dynamic data stream. By using a max heap for the smaller half and a min heap for the larger half, we ensure that the top elements always give us access to the median without needing to sort the entire dataset. This solution is optimal with O(log n) insertion time and O(1) median retrieval, making it ideal for streaming scenarios where data arrives continuously and we need to answer median queries efficiently. The key insight is maintaining the invariant that heap sizes differ by at most one, which guarantees the median can always be found in constant time.