#703 Kth Largest Element in a Stream
frequently reported atAdobeAmazonMetaGoogleMicrosoftGoldman Sachs
the problem
In plain words
Design KthLargest(k, nums) with add(val) that inserts val into the stream and returns the kth largest value seen so far.
in k = 3, nums = [4,5,8,2]; add(3), add(5), add(10), add(9), add(4)
out 4, 5, 5, 8, 8
in k = 4, nums = [7,7,7,7,8,3]; add(2), add(10), add(9), add(9)
out 7, 7, 7, 8
Equal values count separately: the top four after add(10) are 10, 8, 7, 7.
- 0 ≤ nums.length ≤ 10⁴
- 1 ≤ k ≤ nums.length + 1
- -10⁴ ≤ nums[i], val ≤ 10⁴
- At most 10⁴ calls to add
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTop-k with a size-k heap
You never need values smaller than the current kth largest again. Keep only the top k in a min-heap; its root is the answer.
solutions
From brute force to optimal
Keep every value in a sorted ArrayList; the answer is k-th from the end.
- Binary-search the insertion point.
- Insert (shifts the tail).
- Return list[size − k].
Finding the spot is O(log n) but inserting shifts up to n elements.
Stores every value ever added.
class KthLargest { private final List<Integer> sorted = new ArrayList<>(); // every value, ascending private final int k; public KthLargest(int k, int[] nums) { this.k = k; for (int x : nums) insert(x); // may hold fewer than k values for now } public int add(int val) { insert(val); return sorted.get(sorted.size() - k); // k-th from the end } private void insert(int val) { int pos = Collections.binarySearch(sorted, val); if (pos < 0) pos = -pos - 1; // insertion point sorted.add(pos, val); // O(n): shifts the tail right }}Offer each value; if the heap grows past k, poll the smallest. Peek is the kth largest.
- Constructor: add every num the same way.
- add: offer; if size > k poll; return peek.
The heap never holds more than k + 1 values.
Only the top k are kept.
class KthLargest { private final PriorityQueue<Integer> topK = new PriorityQueue<>(); // min-heap of the k largest private final int k; public KthLargest(int k, int[] nums) { this.k = k; for (int x : nums) add(x); } public int add(int val) { topK.offer(val); if (topK.size() > k) topK.poll(); // throw out the smallest: it can never be k-th largest again return topK.peek(); // smallest of the k largest = k-th largest }}Dry run: the same size-k heap
in the room
How to say it in the interview
talk track
- Explain why a MIN-heap: its root is the weakest of the top k, which is exactly the kth largest.
traps
- The initial nums may have fewer than k values (k ≤ n + 1). Don't read the answer in the constructor.
what they ask next
Follow-ups
Why not one max-heap of every value?
To read the kth largest you'd poll k − 1 values and push them back: O(k log n) per add, and memory grows with the whole stream. The size-k min-heap is O(log k) per add and O(k) memory.
What if add is called millions of times but values stay in −10⁴..10⁴?
Count values by number in a Fenwick tree over the 2·10⁴ + 1 possible values. Each add updates one count, and the kth largest is found by walking the tree: O(log V) per call, with V = 20,001.
before you submit
Edge cases to test
- nums has k − 1 values (k = n + 1): the first add completes the top k — don't read an answer in the constructor.
- nums is empty and k = 1: every add returns the largest value so far.
- Duplicates count separately: [7,7,7,7,8,3] with k = 4 answers 7.
practise next
Similar problems
- #215Kth Largest Element in an ArrayMediumin Heaps
- #295Find Median from Data StreamHardin Heaps