Find Median from Data Stream - Practice Coding Problems

Find Median from Data Stream - Problem

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 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⁻⁵ of the actual answer will be accepted.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"], values = [null,1,2,null,3,null]

› Output: [null,null,null,1.5,null,2.0]

💡 Note: Initialize finder, add 1, add 2, find median (1+2)/2=1.5, add 3, find median 2.0

Example 2 — Single Element

$ Input: operations = ["MedianFinder","addNum","findMedian"], values = [null,5,null]

› Output: [null,null,5.0]

💡 Note: With only one element, the median is that element itself

Example 3 — Negative Numbers

$ Input: operations = ["MedianFinder","addNum","addNum","findMedian"], values = [null,-1,-2,null]

› Output: [null,null,null,-1.5]

💡 Note: With -1 and -2, the median is (-1 + -2) / 2 = -1.5

Constraints

-10⁵ ≤ num ≤ 10⁵
There will be at least one element in the data structure before calling findMedian
At most 5 × 10⁴ calls will be made to addNum and findMedian

Visualization

Tap to expand

Understanding the Visualization

Input Stream

Operations: addNum(1), addNum(2), findMedian()

Data Structure

Maintain sorted order or balanced partitions

Output

Return median values: 1.5

Key Takeaway

🎯 Key Insight: Two balanced heaps allow O(log n) insertions with O(1) median queries

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to use two heaps to partition the data stream into smaller and larger halves. The optimal approach uses a max heap for the smaller half and a min heap for the larger half, maintaining balance so that median queries take O(1) time. Time: O(log n) for addNum, O(1) for findMedian. Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Sort Every Time	O(n log n)	O(n)	Store all numbers in a list and sort every time findMedian is called
Two Heaps - Optimal Solution	O(log n)	O(n)	Use max heap for smaller half and min heap for larger half to maintain balance

Brute Force - Sort Every Time — Algorithm Steps

Step 1: Store all numbers in a list as they arrive
Step 2: When median is requested, sort the entire list
Step 3: Return middle element or average of two middle elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Numbers

Store numbers in unsorted list

Find Median

Sort entire list and find middle

Result

Return median value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* nums;
    int size;
    int capacity;
} MedianFinder;

MedianFinder* medianFinderCreate() {
    MedianFinder* mf = (MedianFinder*)malloc(sizeof(MedianFinder));
    mf->capacity = 1000;
    mf->nums = (int*)malloc(mf->capacity * sizeof(int));
    mf->size = 0;
    return mf;
}

void medianFinderAddNum(MedianFinder* obj, int num) {
    if (obj->size >= obj->capacity) {
        obj->capacity *= 2;
        obj->nums = (int*)realloc(obj->nums, obj->capacity * sizeof(int));
    }
    obj->nums[obj->size++] = num;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

double medianFinderFindMedian(MedianFinder* obj) {
    int* sorted = (int*)malloc(obj->size * sizeof(int));
    memcpy(sorted, obj->nums, obj->size * sizeof(int));
    qsort(sorted, obj->size, sizeof(int), compare);
    
    double result;
    if (obj->size % 2 == 1) {
        result = (double)sorted[obj->size / 2];
    } else {
        result = (sorted[obj->size / 2 - 1] + sorted[obj->size / 2]) / 2.0;
    }
    
    free(sorted);
    return result;
}

void medianFinderFree(MedianFinder* obj) {
    free(obj->nums);
    free(obj);
}

int main() {
    printf("[null,null,null,1.5,null,2.0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the list of n elements takes O(n log n) time for each findMedian call

⚡ Linearithmic

Space Complexity

O(n)

Store all n numbers in a list

⚡ Linearithmic Space

78.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Sort Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler