Problem Statement
Continuous Median Tracker
You're building a data analytics system that needs to continuously track the median value of a stream of numbers.
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:
[2,3,4], the median is3[2,3], the median is(2 + 3) / 2 = 2.5
Design a data structure that supports the following operations:
void addNum(int num)- Add an integer from the data stream to the data structure.double findMedian()- Return the median of all elements so far.
Examples
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
- -10^5 <= num <= 10^5
- There will be at least one element in the data structure before calling findMedian.
- At most 5 * 10^4 calls will be made to addNum and findMedian.
Problem Breakdown
To solve this problem, we need to:
- The key challenge is efficiently maintaining the median as new numbers are added to the stream
- Sorting the entire array after each insertion would be inefficient (O(n log n) time complexity)
- Using two heaps (a max heap for the smaller half and a min heap for the larger half) allows for O(log n) insertion and O(1) median retrieval
- The heaps need to be balanced so that their sizes differ by at most 1
- For the follow-up questions, counting sort or bucket sort can be used when the range of numbers is limited
- When most numbers are in a limited range, a combination of counting sort for the limited range and a regular approach for outliers can be efficient
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Continuous Median Tracker
You're building a data analytics system that needs to continuously track the median value of a stream of numbers.
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:
[2,3,4], the median is3[2,3], the median is(2 + 3) / 2 = 2.5
Design a data structure that supports the following operations:
void addNum(int num)- Add an integer from the data stream to the data structure.double findMedian()- Return the median of all elements so far.
Examples
Example 1:
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
Problem Breakdown
Constraints:
- -10^5 <= num <= 10^5
- There will be at least one element in the data structure before calling findMedian.
- At most 5 * 10^4 calls will be made to addNum and findMedian.
Key Insights:
The key challenge is efficiently maintaining the median as new numbers are added to the stream
Sorting the entire array after each insertion would be inefficient (O(n log n) time complexity)
Using two heaps (a max heap for the smaller half and a min heap for the larger half) allows for O(log n) insertion and O(1) median retrieval
The heaps need to be balanced so that their sizes differ by at most 1
For the follow-up questions, counting sort or bucket sort can be used when the range of numbers is limited
When most numbers are in a limited range, a combination of counting sort for the limited range and a regular approach for outliers can be efficient
Real-World Application
This problem has several practical applications:
Real-time Analytics
Calculating median values for streaming data in analytics dashboards.
Data Processing
Processing continuous streams of sensor data in IoT applications.
Financial Systems
Tracking median transaction values or stock prices in financial monitoring systems.
Database Systems
Implementing median aggregate functions in database management systems.
Performance Monitoring
Monitoring median response times or resource usage in system performance tools.