Find Median from Data Stream
Find Median from Data Stream
Design a data structure that reads integers from a stream one by one and returns the current median after each insertion. The median is the middle value of a sorted sequence. For even count, the median is the average of the two middle values. Example: stream [1, 2] → medians: 1, 1.5
Input format — only if your code reads from stdin
Input format: - First line: integer n (number of values in stream) - Second line: n space-separated integers (the stream in order) Output: the median after each number is added, one per line. Print as integer if whole, or as decimal with one decimal place.
Approach
Two heaps: a max-heap for the lower half (lo) and a min-heap for the upper half (hi). Maintain |lo| = |hi| or |lo| = |hi|+1. After each insertion, rebalance. Median = lo.top() if odd count, or (lo.top() + hi.top()) / 2 if even.
Input
Output
- •
1 ≤ n ≤ 5×10^4, -10^5 ≤ stream values ≤ 10^5
More Heaps problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards