Optional: keep only the best k
Use a small min-heap to retain the largest arrivals, and justify the invariant and costs.
Make the weakest retained item easy to discard
To keep the largest k values while reading n arrivals, retain candidates in a min-heap. The goal is largest values, but the next value you may discard is the smallest retained candidate. Push the arrival; if size exceeds k, pop the minimum.
For k = 3 and arrivals 5 1 9 9 2 7, the retained multisets become {5}, {1,5}, {1,5,9}, {5,9,9}, {5,9,9}, and {7,9,9}. This sorted notation explains the set of values; it is not the heap’s physical layout. Duplicate occurrences count separately.
The invariant proves what survives
After every prefix, the heap contains its largest min(k, prefix length) occurrences. Adding one new candidate can create k + 1 candidates; their smallest cannot be needed among their largest k. Previously discarded values do not become more competitive when another value arrives.
With 1 ≤ k ≤ n, the final heap contains exactly k values. Its top is the kth largest occurrence overall. To print all retained values in descending order, pop them into a vector in ascending order and reverse that vector.
Bound the live size, not the entire input
The heap briefly reaches k + 1 values. Each arrival performs heap updates on that bounded size, giving O(n log(k + 1)) amortized time and O(k) logical storage. At k = 1, the algorithm is linear. Keeping a result vector for all k outputs still uses O(k) total logical storage.
If all input is already stored and streaming storage is irrelevant, sorting once can be simpler. The bounded heap is useful when keeping only k candidates saves memory or fits the arrival model.
Finish with the right checks
Test k = 1, k = n, repeated maximum values, all-negative values, and ties around the kth position. For general container simulations, also test an empty request, one insertion then removal, draining to empty, and inserting again afterward.
Choose the operation first: vector for indexing, deque for two ends, queue for oldest-first, stack for newest-first, and a priority queue for changing extrema. Always count copies, removals, comparison costs, and peak simultaneous storage in addition to the visible loop.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
Why use a min-heap when retaining the largest k values?
Turn the idea into code
Read n, k, then n integers with 1 ≤ k ≤ n ≤ 200000. Print the kth largest occurrence, counting duplicates, while using O(k) logical container storage. For 5 1 9 9 2 7 with k = 3, print 7.
Give me a hint
Maintain the largest k arrivals in a min-heap. At the end, its smallest retained value has exactly the required rank.
Show the explained solution
After each arrival, the invariant keeps the largest k occurrences seen so far. The final minimum of those retained values is the kth largest overall. The program does not store the whole input and costs O(n log(k + 1)) amortized time.
// Complete C++23 program. Input: n k, then n integers; 1 <= k <= n.
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
int n = 0, k = 0;
std::cin >> n >> k;
std::priority_queue<int, std::vector<int>, std::greater<int>> best;
for (int i = 0; i < n; ++i) {
int x = 0;
std::cin >> x;
best.push(x);
if (static_cast<int>(best.size()) > k) best.pop();
}
std::cout << best.top() << '\n';
}Your notes
Mark complete when you can explain it yourself.