DSA-075 · Bounded top-k occurrence state across stream updates

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,8
The 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 MAX
No 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.

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.

Streaming kth largest — retained rank and total count

k=3. Total arrivals: 4. Current rank: 4.

Retained largest occurrences — minimum/root first

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.

State after this step
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.

Streaming kth largest — retained rank and total count

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.

State after this step
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.

Streaming kth largest — retained rank and total count

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.

State after this step
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 0
Before readiness.
Input: Add equal negative values
Output: Duplicates count separately
No distinct-key interpretation.
Input: Caller edits initial after construction
Output: Stream query unchanged
Snapshot ownership.
Input: k=MAX, two values
Output: OptionalInt.empty with small memory
No k-sized reservation.
Input: 100,000 increasing arrivals, k=100
Output: Exact bounded rank and full long count
Persistent 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.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 109/20,000 characters

Self-review

I distinguish retained size, total count, and readiness.I keep duplicate occurrences and never return a numeric absence sentinel.I include constructor and baseline query costs, not only add complexity.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Heaps: retain the useful frontier

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external platform-difficulty claims.