75. Kth Largest Element in a Stream
Maintain the kth largest value as new values arrive. The stream includes the initial values and every later addition, with duplicate values counted as separate occurrences.
Until k occurrences exist, use the documented absent-result representation. A query must not consume or discard stream values.
Example 1
Input
k=3, initial=[4,5,8,2], add 3,5,10,9,4
Output
Optional values 4,5,5,8,8
Explanation: The heap keeps three largest occurrences; count reaches nine even though only three values remain retained.
Example 2
Input
k=3, initial=[], add −1,−1,5
Output
empty,empty,OptionalInt[−1]
Explanation: Two equal −1 occurrences both count toward rank.
Example 3
Input
k=1, initial=[MIN], add MAX
Output
current initially MIN, then MAX
Explanation: No numeric sentinel is used for the not-ready state.
Constraints
1 <= k <= 231 - 10 <= total inserted values <= 105-231 <= value <= 231 - 1- The kth-largest value is absent until at least k values have been seen.
Hints
Hint 1
Reuse the batch top-k invariant, but keep the heap between calls.
Hint 2
The root is valid only when at least k occurrences have been seen.
Hint 3
Offer, trim the minimum on overflow, keep a separate total count, and return an explicit optional result.
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.
Persistent top-three updates
3
[4,5,8,2]
[["add",3],["add",5],["add",10],["add",9],["add",4],["count"],["current"]]
[{"present":true,"value":4},{"present":true,"value":5},{"present":true,"value":5},{"present":true,"value":8},{"present":true,"value":8},9,{"present":true,"value":8}]