leetcode.com
Open in
urlscan Pro
2606:4700:20::ac43:48d5
Public Scan
Submitted URL: https://www.encurtador.dev/redirecionamento/fxdhc
Effective URL: https://leetcode.com/problems/find-median-from-data-stream/description/
Submission: On February 06 via api from IL — Scanned from DE
Effective URL: https://leetcode.com/problems/find-median-from-data-stream/description/
Submission: On February 06 via api from IL — Scanned from DE
Form analysis 0 forms found in the DOM
Text Content
*
Problem List
Problem List
RegisterorSign in
Premium
Debugging...
Run
Submit
Description
Description
Editorial
Editorial
Solutions
Solutions
Submissions
Submissions
Code
Code
Testcase
Testcase
Test Result
Test Result
295. Find Median from Data Stream
Hard
Topics
Companies
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?
Accepted
737.8K
Submissions
1.4M
Acceptance Rate
51.8%
--------------------------------------------------------------------------------
Topics
Two PointersDesignSortingHeap (Priority Queue)Data Stream
--------------------------------------------------------------------------------
Companies
--------------------------------------------------------------------------------
Similar Questions
Sliding Window Median
Hard
Finding MK Average
Hard
Sequentially Ordinal Rank Tracker
Hard
--------------------------------------------------------------------------------
Discussion (55)
Choose a type
PreviewComment
💡 Discussion Rules
1. Please don't post any solutions in this discussion.
2. The problem discussion is for asking questions about the problem or for
sharing tips - anything except for solutions.
3. If you'd like to share your solution for feedback and ideas, please head to
the solutions tab and post it there.
Sort by:Best
nupt_wang
Apr 15, 2019
1. If all integer numbers from the stream are between 0 and 100, how would you
optimize it?
We can maintain an integer array of length 100 to store the count of each number
along with a total count. Then, we can iterate over the array to find the middle
value to get our median.
Time and space complexity would be O(100) = O(1).
2. If 99% of all integer numbers from the stream are between 0 and 100, how
would you optimize it?
In this case, we need an integer array of length 100 and a hashmap for these
numbers that are not in [0,100].
Read more
401
Show 14 Replies
Reply
vyshnavkr
Mar 14, 2021
Important posts from discussions:
* I was asked this question in an interview today. I told about the minHeap and
maxHeap approach. The interviewer asked what if the data is very very large.
How would you handle it? Any thoughts?!
* https://leetcode.com/problems/find-median-from-data-stream/discuss/228442/Java-Solution-with-Tree-O(Log-N)-Insertion-and-Lookup-+-Explanation
: Java Solution with Tree - O(Log N) Insertion and Lookup + Explanation
* https://leetcode.com/problems/find-median-from-data-stream/discuss/111698/Be-asked-for-a-multi-thread-and-thread-safe-solution-in-a-real-interview.
: Be asked for a multi-thread and thread-safe solution in a real interview
* https://leetcode.com/problems/find-median-from-data-stream/discuss/652498/Good-for-interviews:-Python-general-sort-greater-insertion-sort-greater-two-heaps-greater-follow-ups
: Good for interviews: Python general sort -> insertion sort -> two heaps ->
follow-ups
Observations:
* The change in Median: when a new element comes, the new median will be either
1 unit left or 1 unit right to the prvious median. We use 2 pointers to
implement this along with taking care of average of middle numbers for even
size.
* Median means sorted data and middle element(s). Sorted data means
'array/collection + manual sort' or self balanced bst or miltuple heaps or
monotonic stack or deque (which isn't useful for this problem since monotonic
stack/deque will involve removal exisiting elements).
* Heap utilities:
* using a heap for a data set helps to get the smallest/largest element
fastly
* using 2 heaps: if we divide the random data (non sorted data) into 2 heaps
(1 min and other max) such that the first half of sorted data (data if it
had been sorted) is in max heap and second half of sorted data (data if it
had been sorted) is in min heap, we could easily get the middle element of
the sorted data (data if it had been sorted). VISUALIZE!!!
Read more
37
Show 2 Replies
Reply
chao4
Sep 27, 2018
In real world streaming application. The data amount will be huge so it is
impossible to hold all the data in the stream into memory.
I think it is a good open-end question to ask. What if the memory is not allowed
to hold all the data from the beginning. Some data needs to go to hard drive.
How will we optmize that.
Read more
27
Show 2 Replies
Reply
Future6
Nov 08, 2017
["MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"]
[[],[6],[],[10],[],[2],[],[6],[],[5],[],[0],[],[6],[],[3],[],[1],[],[0],[],[0],[]]
so the list is {6, 10, 2, 6, 5, 0, 6, 3, 1, 0, 0}
and the MedianFinder result should be: 6, 8, 10, 6, 2, 4, 6, 5.5, 5, 2.5, 0
But it offers answer as follows:
[null,null,6.00000,null,8.00000,null,6.00000,null,6.00000,null,6.00000,null,5.50000,null,6.00000,null,5.50000,null,5.00000,null,4.00000,null,3.00000]
Or I misunderstand this quesiton
Read more
26
Show 3 Replies
Reply
Msey
Apr 02, 2023
Wanted to complete it quickly by using Sorting instead of two heaps and got TLE
haha
Read more
20
Reply
prakashsellathurai
Mar 28, 2022
1. If all integer numbers from the stream are in the range [0, 100], how would
you optimize your solution?
Since the input range is bounded we can use counter array to calculate median,
where count[i] represents the number of times integer data occur in the stream
in O(1) space and time
refer this problem: statistics-from-a-large-sample
2. If 99% of all integer numbers from the stream are in the range [0, 100], how
would you optimize your solution?
IF 99% of all integers from the stream are in the range [0,100] then considering
empirical rule
"99.7% of data observed following a normal distribution lies within 3 standard
deviations of the mean"
we can assume that the input stream is normally distributed in this case.
If we maintain a reservoir of 100 items sampled with equal probability stored in
a array then we can estimate the median of the the input data with highest
confidence for large input data distribution of unknown size .
Alternate Interesting Solution: By using median filter stackoverflow
Read more
13
Reply
54564269
Jan 28, 2018
Got it done pretty soon using 2 heaps in a real interview. However, in the
follow-up, I'm asked how to improve it and make sure the method is thread-safe
if the two heaps are shared.
Read more
13
Show 3 Replies
Reply
bayernkang
Aug 07, 2020
Should I implement the Heap data structure myself ? (that's a lot of code to
memorize and write).
Do anyone encounter a quesiton in a real interview that have to use heap but you
are using Javascript?
Read more
7
Reply
mukunda-
May 02, 2020
Don't build your algorithm around a counting sort due to the "hints": If 99% of
all integer numbers from the stream are between 0 and 100, how would you
optimize it?
Some of the tests do not follow this at all.
Read more
7
Reply
suziray
Apr 09, 2016
I saw there is some solution for using BST in C++, and I heard some hint for
using Counting Sort or maintaining the median and the numbers next to it. Is
there a way to do these in Java?
Additionally, another version is to return the median of recent k numbers added,
how could this be achieved...
Read more
6
Show 1 Replies
Reply
123456
Copyright ©️ 2024 LeetCode All rights reserved
11.5K
55
C++
Auto
1
c
Ln 1, Col 1
You need to Login / Sign up to run or submit
Case 1
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
1
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
Source
FindHeaderBarSize
FindTabBarSize
FindBorderBarSize
Introducing Dynamic LayoutNEW
Unleash your potential with the immersive and flexible coding environment
Show Run & Submit buttons in
ToolBar
Code Editor
You can change the preference at any time in the settings
Enable Dynamic Layout
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word word word word word word word word word
word word word word word word word word
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1