73. Find Median from Data Stream
Maintain a growing stream of integer values and answer the median after additions. For an odd count the median is the middle value; for an even count it is the average of the two middle values.
Queries do not remove values. The empty-stream median operation has the explicit exception behavior given in the contract.
Example 1
Input
add 5, add 1, add 9, add 2; median after each
Output
5.0,3.0,5.0,3.5
Explanation: The two roots supply the central pair while each insertion repairs size balance.
Example 2
Input
add MIN, add MAX; median
Output
−0.5
Explanation: Long addition avoids int overflow and /2.0 avoids truncation.
Example 3
Input
median on a new instance
Output
NoSuchElementException; size remains 0
Explanation: No numeric sentinel can represent every valid median plus absence.
Constraints
0 <= inserted values <= 105-231 <= value <= 231 - 1- Querying the median requires at least one inserted value.
Hints
Hint 1
Can the two central ranks be exposed without sorting all values?
Hint 2
Keep a max-heap below the median and a min-heap above it.
Hint 3
Route by the lower root, transfer one boundary root if sizes differ incorrectly, then peek the middle value(s).
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Insertion, balancing, and empty/read outcomes
[["median"],["add",5],["add",1],["median"],["add",9],["median"],["add",2],["median"],["size"]]
["NoSuchElementException",null,null,3,null,5,null,3.5,4]