Find Median from Data Stream
Hard Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: How can we efficiently find the median from a stream of incoming data?, Priority Queue, Heap, Stream Processing, priority queue, binary search, sorting algorithms, algorithm design, array algorithms, Streaming Data / Running Median.
Median from Data Stream Problem Statement: Design a data structure that supports adding integers from a data stream and finding the median of the current elements. The median is the middle value in an ordered integer list. If the size of the list is even, the median is the average of the two middle numbers. Operations: 1. addNum(int num): Adds an integer num to the data structure. 2. findMedian(): Returns the median of all elements added so far. Constraints: 10^5 ≤ num ≤ 10^5 At most 10^4 calls will be made collectively to addNum and findMedian. Sample Input/Output: Difficulty: Medium Solution Approaches Two Heaps Approach (Priority Queues) 1. Concept: Maintain two heaps: A max heap for the lower half of numbers (left partition) A min heap for the upper half (right partition) 2. Balancing: Ensure the heaps differ by at most 1 element. Always keep the left heap equal or 1 greater than the right. 3. Insertion: If heaps are empty, add to left. If num ≤ left.max, add to left. Otherwise, add to right. Rebalance if necessary by moving the root of the larger heap to the other. 4. Median Calculation: Odd total elements: Root of left heap. Even total elements: Average of both roots. 5. Complexity: Time: O(log n) per insertion (heap operations). O(1) for median lookup. Space: O(n) for storing all elements.