DSA-075 · FOCUSED PRACTICE
Kth Largest Element in a Stream
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 199225 deterministic checks. Learner drafts are not executed.
Understand the problem
Implement KthLargest(k,initial), add(int), current(), and count() for an insert-only int stream. Count duplicate occurrences separately and report the kth largest only after at least k values exist.
- k must be positive; invalid k throws IllegalArgumentException. initial must be nonnull, otherwise NullPointerException. Each instance processes at most 100,000 values across construction and additions; k may exceed the current or eventual count, including Integer.MAX_VALUE.
- add returns OptionalInt.empty until k values have arrived, then OptionalInt.of(the kth-largest occurrence). current returns the same type without adding or consuming a value. count is a long total including constructor values, not the retained heap size.
- Input initial is read-only and its values are snapshotted into instance state; later caller array edits do not change the stream. Instances are mutable and not thread-safe. Retained data are values, not references into the caller array.
Examples
Input:
k=3, initial=[4,5,8,2], add 3,5,10,9,4
Output:Optional values 4,5,5,8,8The heap keeps three largest occurrences; count reaches nine even though only three values remain retained.
Input:
k=3, initial=[], add −1,−1,5
Output:empty,empty,OptionalInt[−1]Two equal −1 occurrences both count toward rank.
Input:
k=1, initial=[MIN], add MAX
Output:current initially MIN, then MAXNo numeric sentinel is used for the not-ready state.
Before you start
- Kth-largest heap invariant (DSA-069)
- Explicit absence with OptionalInt and constructor snapshots
Recognize the structure
The batch kth-largest problem becomes a persistent invariant: after every insertion retain only the largest k occurrences. Smaller discarded values cannot become relevant again in an insert-only stream. Deletions or changing k would invalidate that sufficiency argument.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 109/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
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.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Retain all values and sort a copy per rank query
Store every occurrence. For current(), return empty when fewer than k exist; otherwise sort a copied history descending and select index k−1. With k=3 and [4,5,8,2], sorted history is [8,5,4,2], yielding 4. This is O(m log(m+1)) per nonempty rank query at m values and O(m) retained history, contrasting with the bounded heap’s O(1) current query.
Improve the baseline
Initialize using ordinary additions
Validate k and initial, then feed each constructor value through add. Do not reserve k heap slots up front: a huge k with a tiny stream still needs only tiny state.
Keep the largest min(k,count) occurrences
Offer each new value to a min-heap and poll its smallest if size exceeds k. Increment the independent total count for every arrival, including those immediately discarded.
Separate readiness from numeric rank
If heap size<k, no kth value exists yet and current returns OptionalInt.empty. Otherwise its root is the smallest of the retained largest k, exactly the kth-largest occurrence.
Why it is correct
Initialization and snapshot
The empty heap contains the largest zero occurrences. Repeated constructor additions establish the same invariant as later calls, copying primitive values so later source-array edits cannot affect retained state.
Preservation
Adding one occurrence introduces the only new candidate for the top k. If size becomes k+1, discarding the smallest leaves the largest k including multiplicity. In an insert-only stream a discarded occurrence can never outrank the k retained ones later.
Queries and counts
Before readiness, fewer than k total occurrences exist. After readiness, root rank is exactly kth largest by the selection invariant. peek/current do not modify state, while the separate seen count records all arrivals rather than only retained values.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Objects;
import java.util.OptionalInt;
import java.util.PriorityQueue;
public final class Solution {
public static final class KthLargest {
private final int k;
private final PriorityQueue<Integer> largest = new PriorityQueue<>();
private long seen;
public KthLargest(int k, int[] initial) {
if (k <= 0) throw new IllegalArgumentException("k must be positive");
Objects.requireNonNull(initial, "initial");
this.k = k;
for (int value : initial) add(value);
}
public OptionalInt add(int value) {
seen++;
largest.offer(value);
if (largest.size() > k) largest.poll();
return current();
}
public OptionalInt current() {
return largest.size() < k ? OptionalInt.empty() : OptionalInt.of(largest.peek());
}
public long count() { return seen; }
}
public static final class Baseline {
private final int k;
private final ArrayList<Integer> all = new ArrayList<>();
public Baseline(int k, int[] initial) {
if (k <= 0) throw new IllegalArgumentException("k must be positive");
Objects.requireNonNull(initial, "initial");
this.k = k;
for (int value : initial) all.add(value);
}
public OptionalInt add(int value) { all.add(value); return current(); }
public OptionalInt current() {
if (all.size() < k) return OptionalInt.empty();
ArrayList<Integer> sorted = new ArrayList<>(all);
sorted.sort(Comparator.reverseOrder());
return OptionalInt.of(sorted.get(k-1));
}
public long count() { return all.size(); }
}
}
Read the meaningful blocks
No enormous initial capacity
PriorityQueue is created with default capacity; k is a rank bound, not a command to allocate k entries immediately.
Offer, trim, and report
The returned OptionalInt is computed after trimming. A rejected small value still increments seen and must not disappear from the total count.
Use value multiplicity
A set would implement kth distinct value, not this API. Equal values remain separate heap entries.
Complexity
After m arrivals, add is O(log(min(k,m)+1)) heap work plus constant reporting; use O(log(k+1)) as a uniform bound. current and count are O(1), with O(min(k,m)) retained values. Constructor feeding n values costs O(n log(min(k,n)+1)).
The baseline retains O(m) values and sorts O(m) temporary query storage in O(m log(m+1)) time once ready; add invokes that query after appending. Before readiness its query is O(1). Exact rank under deletions requires additional state.
Exact-state walkthroughs
Reveal normal and boundary traces
Persistent top-three updates
Input: {"k":3,"initial":[4,5,8,2],"operations":[["add",3],["add",5],["add",10],["add",9],["add",4],["count"],["current"]]} · Operation outcomes: [{"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}]
Step 1 of 9: Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
k=3. Total arrivals: 4. Current rank: 4.
Retained largest occurrences — minimum/root first
- 4
- 5
- 8
Duplicates occupy separate rank positions. Total count includes values that were discarded; it is not the retained queue size. present:false in outcomes means no kth occurrence exists yet.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| k | 3 |
| initial | [4,5,8,2] |
| retainedValues | [4,5,8] |
| count | 4 |
| currentRank | {"present":true,"value":4} |
| outcomes | [] |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.OptionalInt; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class KthLargest { 8 private final int k; 9 private final PriorityQueue<Integer> largest = new PriorityQueue<>(); 10 private long seen; 11 public KthLargest(int k, int[] initial) { 12 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 13 Objects.requireNonNull(initial, "initial"); 14 this.k = k; 15 for (int value : initial) add(value); 16 } 17 public OptionalInt add(int value) { 18 seen++; 19 largest.offer(value); 20 if (largest.size() > k) largest.poll(); 21 return current(); 22 } 23 public OptionalInt current() { 24 return largest.size() < k ? OptionalInt.empty() : OptionalInt.of(largest.peek()); 25 } 26 public long count() { return seen; } 27 } 28 public static final class Baseline { 29 private final int k; 30 private final ArrayList<Integer> all = new ArrayList<>(); 31 public Baseline(int k, int[] initial) { 32 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 33 Objects.requireNonNull(initial, "initial"); 34 this.k = k; 35 for (int value : initial) all.add(value); 36 } 37 public OptionalInt add(int value) { all.add(value); return current(); } 38 public OptionalInt current() { 39 if (all.size() < k) return OptionalInt.empty(); 40 ArrayList<Integer> sorted = new ArrayList<>(all); 41 sorted.sort(Comparator.reverseOrder()); 42 return OptionalInt.of(sorted.get(k-1)); 43 } 44 public long count() { return all.size(); } 45 } 46 } 47
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
- k
3- initial
[4,5,8,2]- retainedValues
[4,5,8]- count
4- currentRank
{"present":true,"value":4}- outcomes
[]- phase
"initial"
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[4,5,8]- count
5- currentRank
{"present":true,"value":4}- outcomes
[{"present":true,"value":4}]- phase
"operation"- index
0- operation
"add"- value
3- discarded
3- outcome
{"present":true,"value":4}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[5,5,8]- count
6- currentRank
{"present":true,"value":5}- outcomes
[{"present":true,"value":4},{"present":true,"value":5}]- phase
"operation"- index
1- operation
"add"- value
5- discarded
4- outcome
{"present":true,"value":5}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[5,8,10]- count
7- currentRank
{"present":true,"value":5}- outcomes
[{"present":true,"value":4},{"present":true,"value":5},{"present":true,"value":5}]- phase
"operation"- index
2- operation
"add"- value
10- discarded
5- outcome
{"present":true,"value":5}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[8,9,10]- count
8- currentRank
{"present":true,"value":8}- outcomes
[{"present":true,"value":4},{"present":true,"value":5},{"present":true,"value":5},{"present":true,"value":8}]- phase
"operation"- index
3- operation
"add"- value
9- discarded
5- outcome
{"present":true,"value":8}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[8,9,10]- count
9- currentRank
{"present":true,"value":8}- outcomes
[{"present":true,"value":4},{"present":true,"value":5},{"present":true,"value":5},{"present":true,"value":8},{"present":true,"value":8}]- phase
"operation"- index
4- operation
"add"- value
4- discarded
4- outcome
{"present":true,"value":8}
- Apply count with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[8,9,10]- count
9- currentRank
{"present":true,"value":8}- outcomes
[{"present":true,"value":4},{"present":true,"value":5},{"present":true,"value":5},{"present":true,"value":8},{"present":true,"value":8},9]- phase
"operation"- index
5- operation
"count"- discarded
null- outcome
9
- Apply current with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[4,5,8,2]- retainedValues
[8,9,10]- count
9- currentRank
{"present":true,"value":8}- outcomes
[{"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}]- phase
"operation"- index
6- operation
"current"- discarded
null- outcome
{"present":true,"value":8}
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[{"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}]
Optional absence until enough duplicates arrive
Input: {"k":3,"initial":[],"operations":[["current"],["add",-1],["add",-1],["add",5],["current"],["count"]]} · Operation outcomes: [{"present":false},{"present":false},{"present":false},{"present":true,"value":-1},{"present":true,"value":-1},3]
Step 1 of 8: Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
k=3. Total arrivals: 0. Current rank: OptionalInt.empty.
Retained largest occurrences — minimum/root first
Empty.
Duplicates occupy separate rank positions. Total count includes values that were discarded; it is not the retained queue size. present:false in outcomes means no kth occurrence exists yet.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| k | 3 |
| initial | [] |
| retainedValues | [] |
| count | 0 |
| currentRank | {"present":false} |
| outcomes | [] |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.OptionalInt; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class KthLargest { 8 private final int k; 9 private final PriorityQueue<Integer> largest = new PriorityQueue<>(); 10 private long seen; 11 public KthLargest(int k, int[] initial) { 12 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 13 Objects.requireNonNull(initial, "initial"); 14 this.k = k; 15 for (int value : initial) add(value); 16 } 17 public OptionalInt add(int value) { 18 seen++; 19 largest.offer(value); 20 if (largest.size() > k) largest.poll(); 21 return current(); 22 } 23 public OptionalInt current() { 24 return largest.size() < k ? OptionalInt.empty() : OptionalInt.of(largest.peek()); 25 } 26 public long count() { return seen; } 27 } 28 public static final class Baseline { 29 private final int k; 30 private final ArrayList<Integer> all = new ArrayList<>(); 31 public Baseline(int k, int[] initial) { 32 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 33 Objects.requireNonNull(initial, "initial"); 34 this.k = k; 35 for (int value : initial) all.add(value); 36 } 37 public OptionalInt add(int value) { all.add(value); return current(); } 38 public OptionalInt current() { 39 if (all.size() < k) return OptionalInt.empty(); 40 ArrayList<Integer> sorted = new ArrayList<>(all); 41 sorted.sort(Comparator.reverseOrder()); 42 return OptionalInt.of(sorted.get(k-1)); 43 } 44 public long count() { return all.size(); } 45 } 46 } 47
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
- k
3- initial
[]- retainedValues
[]- count
0- currentRank
{"present":false}- outcomes
[]- phase
"initial"
- Apply current with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[]- count
0- currentRank
{"present":false}- outcomes
[{"present":false}]- phase
"operation"- index
0- operation
"current"- discarded
null- outcome
{"present":false}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[-1]- count
1- currentRank
{"present":false}- outcomes
[{"present":false},{"present":false}]- phase
"operation"- index
1- operation
"add"- value
-1- discarded
null- outcome
{"present":false}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[-1,-1]- count
2- currentRank
{"present":false}- outcomes
[{"present":false},{"present":false},{"present":false}]- phase
"operation"- index
2- operation
"add"- value
-1- discarded
null- outcome
{"present":false}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[-1,-1,5]- count
3- currentRank
{"present":true,"value":-1}- outcomes
[{"present":false},{"present":false},{"present":false},{"present":true,"value":-1}]- phase
"operation"- index
3- operation
"add"- value
5- discarded
null- outcome
{"present":true,"value":-1}
- Apply current with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[-1,-1,5]- count
3- currentRank
{"present":true,"value":-1}- outcomes
[{"present":false},{"present":false},{"present":false},{"present":true,"value":-1},{"present":true,"value":-1}]- phase
"operation"- index
4- operation
"current"- discarded
null- outcome
{"present":true,"value":-1}
- Apply count with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
3- initial
[]- retainedValues
[-1,-1,5]- count
3- currentRank
{"present":true,"value":-1}- outcomes
[{"present":false},{"present":false},{"present":false},{"present":true,"value":-1},{"present":true,"value":-1},3]- phase
"operation"- index
5- operation
"count"- discarded
null- outcome
3
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[{"present":false},{"present":false},{"present":false},{"present":true,"value":-1},{"present":true,"value":-1},3]
Rank one across integer extremes
Input: {"k":1,"initial":[-2147483648],"operations":[["current"],["add",2147483647],["count"]]} · Operation outcomes: [{"present":true,"value":-2147483648},{"present":true,"value":2147483647},2]
Step 1 of 5: Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
k=1. Total arrivals: 1. Current rank: -2147483648.
Retained largest occurrences — minimum/root first
- -2147483648
Duplicates occupy separate rank positions. Total count includes values that were discarded; it is not the retained queue size. present:false in outcomes means no kth occurrence exists yet.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| k | 1 |
| initial | [-2147483648] |
| retainedValues | [-2147483648] |
| count | 1 |
| currentRank | {"present":true,"value":-2147483648} |
| outcomes | [] |
| phase | "initial" |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.Objects; 4 import java.util.OptionalInt; 5 import java.util.PriorityQueue; 6 public final class Solution { 7 public static final class KthLargest { 8 private final int k; 9 private final PriorityQueue<Integer> largest = new PriorityQueue<>(); 10 private long seen; 11 public KthLargest(int k, int[] initial) { 12 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 13 Objects.requireNonNull(initial, "initial"); 14 this.k = k; 15 for (int value : initial) add(value); 16 } 17 public OptionalInt add(int value) { 18 seen++; 19 largest.offer(value); 20 if (largest.size() > k) largest.poll(); 21 return current(); 22 } 23 public OptionalInt current() { 24 return largest.size() < k ? OptionalInt.empty() : OptionalInt.of(largest.peek()); 25 } 26 public long count() { return seen; } 27 } 28 public static final class Baseline { 29 private final int k; 30 private final ArrayList<Integer> all = new ArrayList<>(); 31 public Baseline(int k, int[] initial) { 32 if (k <= 0) throw new IllegalArgumentException("k must be positive"); 33 Objects.requireNonNull(initial, "initial"); 34 this.k = k; 35 for (int value : initial) all.add(value); 36 } 37 public OptionalInt add(int value) { all.add(value); return current(); } 38 public OptionalInt current() { 39 if (all.size() < k) return OptionalInt.empty(); 40 ArrayList<Integer> sorted = new ArrayList<>(all); 41 sorted.sort(Comparator.reverseOrder()); 42 return OptionalInt.of(sorted.get(k-1)); 43 } 44 public long count() { return all.size(); } 45 } 46 } 47
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Feed constructor values through the ordinary bounded update.
Retained values are min-priority first; count includes discarded values. No k-sized reservation or input-array alias is retained.
- k
1- initial
[-2147483648]- retainedValues
[-2147483648]- count
1- currentRank
{"present":true,"value":-2147483648}- outcomes
[]- phase
"initial"
- Apply current with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
1- initial
[-2147483648]- retainedValues
[-2147483648]- count
1- currentRank
{"present":true,"value":-2147483648}- outcomes
[{"present":true,"value":-2147483648}]- phase
"operation"- index
0- operation
"current"- discarded
null- outcome
{"present":true,"value":-2147483648}
- Apply add with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
1- initial
[-2147483648]- retainedValues
[2147483647]- count
2- currentRank
{"present":true,"value":2147483647}- outcomes
[{"present":true,"value":-2147483648},{"present":true,"value":2147483647}]- phase
"operation"- index
1- operation
"add"- value
2147483647- discarded
-2147483648- outcome
{"present":true,"value":2147483647}
- Apply count with explicit rank readiness.
The heap retains the largest min(k,count) occurrences. A present:false record means OptionalInt.empty, never a numeric sentinel.
- k
1- initial
[-2147483648]- retainedValues
[2147483647]- count
2- currentRank
{"present":true,"value":2147483647}- outcomes
[{"present":true,"value":-2147483648},{"present":true,"value":2147483647},2]- phase
"operation"- index
2- operation
"count"- discarded
null- outcome
2
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[{"present":true,"value":-2147483648},{"present":true,"value":2147483647},2]
Test the contract
Input:
k=3, empty seed
Output:current empty, count 0Before readiness.
Input:
Add equal negative values
Output:Duplicates count separatelyNo distinct-key interpretation.
Input:
Caller edits initial after construction
Output:Stream query unchangedSnapshot ownership.
Input:
k=MAX, two values
Output:OptionalInt.empty with small memoryNo k-sized reservation.
Input:
100,000 increasing arrivals, k=100
Output:Exact bounded rank and full long countPersistent state boundary.
Common mistakes and counterexamples
Return the smallest available value before k arrivals
Counterexample: For k=3 and only [5], no third-largest occurrence exists.
Return OptionalInt.empty, not a fabricated number or heap root.
Expose heap size as total count
Counterexample: After 100 arrivals with k=3, retained size is three but count must be 100.
Track arrivals separately.
Use a set to save duplicates
Counterexample: [5,5,1] with k=2 has kth largest 5, not 1.
Retain occurrences, not distinct keys.
Preallocate capacity k
Counterexample: k=MAX with an empty stream would request huge unnecessary memory.
Use incremental heap storage bounded by actual arrivals.
Follow-ups
Report the kth distinct value.
Define duplicate suppression and retain a membership structure. Counts/history semantics differ from kth occurrence, and memory can exceed k if future transitions or deletions matter.
Support a larger k later.
Values previously discarded may become necessary. A fixed-k heap cannot reconstruct them; retain more history, cap changes by a known maximum rank, or use another order-statistic structure.
Merge two fixed-k summaries.
For the same k, the global top k is contained in the union of each summary’s retained top k. Merge those multisets, trim, and add total counts; insufficient-history readiness and occurrence multiplicity still matter.