Scale Engineer

Find Median from Data Stream

Hard
#0282Time: `addNum(num)`: O(1) amortized time. `findMedian()`: O(N log N) time due to sorting the list of N elements.Space: O(N), where N is the number of elements added to the stream. We need to store all the numbers.23 companies
Patterns
Two PointersDesignData Stream
Algorithms
Sorting
Data structures
Heap (Priority Queue)
Companies
AgodaDocusignGoldman SachsGoogle

Prompt

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

 

Constraints:

  • -105 <= num <= 105
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 104 calls will be made to addNum and findMedian.

 

Follow up:

  • If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
  • If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward and intuitive approach. We store all the numbers that have been added to the stream in a dynamic array (or a list). When addNum is called, we simply append the new number to our list. When findMedian is called, we first sort the list and then find the middle element(s) to calculate the median. While simple, this method is highly inefficient for the findMedian operation, as sorting takes O(N log N) time, where N is the current number of elements in the stream.

Algorithm

  • Data Structure: Use a simple list (like ArrayList in Java) to store the numbers from the data stream.
  • addNum(int num) Operation:
    • Simply append the new number num to the end of the list.
  • findMedian() Operation:
    1. Sort the entire list in non-decreasing order.
    2. Determine the size of the list, n.
    3. If n is odd, the median is the element at the middle index, n / 2.
    4. If n is even, the median is the average of the two middle elements at indices n / 2 - 1 and n / 2.

Walkthrough

In this approach, we use an ArrayList to keep all the numbers. The addNum method is very fast, as it just involves adding an element to the end of the list, which is an O(1) amortized operation. The main drawback is the findMedian method. To find the median, we must first have the numbers in sorted order. Therefore, every call to findMedian requires sorting the entire list. After sorting, we can easily access the middle element(s) in O(1) time to compute the median.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class MedianFinder {    private List<Integer> store;     /** initialize your data structure here. */    public MedianFinder() {        store = new ArrayList<>();    }     public void addNum(int num) {        store.add(num);    }     public double findMedian() {        Collections.sort(store);        int n = store.size();        if (n % 2 != 0) {            // Odd number of elements            return (double) store.get(n / 2);        } else {            // Even number of elements            int mid1 = store.get(n / 2 - 1);            int mid2 = store.get(n / 2);            return (double) (mid1 + mid2) / 2.0;        }    }}

Complexity

Time

`addNum(num)`: O(1) amortized time. `findMedian()`: O(N log N) time due to sorting the list of N elements.

Space

O(N), where N is the number of elements added to the stream. We need to store all the numbers.

Trade-offs

Pros

  • Very simple to understand and implement.

  • The addNum operation is fast (amortized O(1)).

Cons

  • findMedian operation is very inefficient due to sorting the entire list every time it's called.

  • This approach will be too slow and likely time out for large numbers of calls, as specified in the problem constraints.

Solutions

public class MedianFinder { private List < int > nums ; private int curIndex ; /** initialize your data structure here. */ public MedianFinder () { nums = new List < int >(); } private int FindIndex ( int val ) { int left = 0 ; int right = nums . Count - 1 ; while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( val > nums [ mid ]) { left = mid + 1 ; } else { right = mid - 1 ; } } return left ; } public void AddNum ( int num ) { if ( nums . Count == 0 ) { nums . Add ( num ); curIndex = 0 ; } else { curIndex = FindIndex ( num ); if ( curIndex == nums . Count ) { nums . Add ( num ); } else { nums . Insert ( curIndex , num ); } } } public double FindMedian () { if ( nums . Count % 2 == 1 ) { return ( double ) nums [ nums . Count / 2 ]; } else { if ( nums . Count == 0 ) { return 0 ; } else { return ( double ) ( nums [ nums . Count / 2 - 1 ] + nums [ nums . Count / 2 ]) / 2 ; } } } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.AddNum(num); * double param_2 = obj.FindMedian(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem