SyntaxPilot
Courses/C++ Coding Questions/Lesson 18
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 18 of 30

Heap questions

k largest elements (min-heap of size k)k-th smallestmerge k sorted vectors (priority_queue with greater<>)

These are the notes for C++ Coding Questions, episode 18, placement practice for people who finished the SyntaxPilot C++ course. The heap, which always keeps the best item on top, on three of the most asked interview questions: the k largest elements (a min-heap of size k, and why the default max-heap keeps exactly the wrong ones), the k-th smallest (why a set loses duplicates), and merging k sorted vectors (a heap of fronts, and the empty-list crash).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In C++
A hospital emergency room: the most serious patient is seen first a priority queue (heap): top() is the best
Picking the top 3 run-scorers: the weakest selected player sits in the guard chair by the door the k largest: a min-heap of size k, top() is the weakest kept
A new player only has to beat the guard compare with pq.top(); pop() throws out the weakest
The 3rd shortest child in a photo, twins included the k-th smallest, duplicates count
Writing down only the different heights a set: each value once
The principal looks only at the top sheet of each teacher's sorted pile merge k lists: a heap of the k fronts
A teacher who handed in no sheets an empty vector has no [0]

A heap in one minute: priority_queue

#include <queue>
priority_queue<int> pq;                                 // MAX-heap: top() is the largest
pq.push(5);  pq.top();  pq.pop();  pq.size();  pq.empty();

priority_queue<int, vector<int>, greater<int>> mn;     // MIN-heap: top() is the smallest
  • push and pop are O(log n); top, size and empty are O(1).
  • The second template argument, vector<int>, is where the values are stored; the third, the comparator greater<int>, flips the order. greater<> (empty brackets) works for any type that has >, such as pair or tuple.
  • pop() removes the top: the largest in a max-heap, the smallest in a min-heap.

What a heap looks like inside

A binary heap is a binary tree where every parent is ≥ its children (max-heap), so the largest is at the root. It is stored in a plain vector: the children of index i are at 2i + 1 and 2i + 2.

        12
      /    \
     5      11        stored in a vector:  12 5 11 3 1 2
    / \    /
   3   1  2

push adds at the end and swaps up while bigger than its parent; pop moves the last value to the root and swaps it down. The tree has about log₂ n levels, so both are O(log n). The same operations exist as functions on a plain vector: make_heap, push_heap, pop_heap.

Q1: The k largest elements

Problem. Given n numbers and k, print the k largest, the smallest of them first.

Input Output
3 1 5 12 2 11, k = 3 5 11 12

Think out loud. Edge cases: k = n, duplicates. Big test (0 0): 1,000,000 numbers (a shuffle of 0 … 999,999), k = 100,000; the program prints how many were kept and the smallest of them.

The obvious attempt: find the max and erase it, k times

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> kLargest(vector<int> a, int k) {
    vector<int> top;
    for (int t = 0; t < k; t++) {
        auto it = max_element(a.begin(), a.end());
        top.push_back(*it);
        a.erase(it);                     // take the biggest out
    }
    reverse(top.begin(), top.end());     // smallest first
    return top;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 100,000
        n = 1000000; k = 100000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
    }
    vector<int> top = kLargest(a, k);
    if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
    for (int x : top) cout << x << " ";
    cout << "\n";
    return 0;
}
5 11 12 

On the big test:

Time Limit Exceeded

100,000 rounds, each scanning up to a million numbers, and erase shifts the rest too: around 100,000,000,000 steps. O(n · k).

Attempt: a heap of size k, with the default priority_queue<int>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> kLargest(const vector<int>& a, int k) {
    priority_queue<int> pq;
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();   // too many: drop one
    }
    vector<int> top;
    while (!pq.empty()) { top.push_back(pq.top()); pq.pop(); }
    return top;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 100,000
        n = 1000000; k = 100000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
    }
    vector<int> top = kLargest(a, k);
    if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
    for (int x : top) cout << x << " ";
    cout << "\n";
    return 0;
}
3 2 1 

3 2 1: the three smallest. After 3 1 5 12 the heap has 4 values; pop() removes the top, and in a max-heap the top is 12, the best player.

Fix: a min-heap, greater<int>

To keep the k largest, the heap must throw out the weakest: a min-heap, whose top is the smallest kept value (the guard chair).

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> kLargest(const vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;   // min-heap
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();   // too many: drop one
    }
    vector<int> top;
    while (!pq.empty()) { top.push_back(pq.top()); pq.pop(); }
    return top;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 1,000,000 numbers, k = 100,000
        n = 1000000; k = 100000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = (i * 7919LL) % n;
    }
    vector<int> top = kLargest(a, k);
    if (n > 20) { cout << top.size() << " kept, smallest " << top[0] << "\n"; return 0; }
    for (int x : top) cout << x << " ";
    cout << "\n";
    return 0;
}
5 11 12 

The big test, instantly:

100000 kept, smallest 900000

O(n log k) time (the heap never holds more than k + 1 values), O(k) space. When n is huge and k small (the top 10 of a billion log lines), this is far better than sorting everything.

Q2: The k-th smallest element

Problem. Given n numbers and k, print the k-th smallest. Duplicates count.

Input Output
7 10 4 3 20 15, k = 3 7 (3 4 7)
7 10 4 3 20 15 4, k = 3 4 (3 4 4)

The obvious attempt: a set

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int kthSmallest(const vector<int>& a, int k) {
    set<int> s(a.begin(), a.end());      // sorted
    auto it = s.begin();
    advance(it, k - 1);                  // step to the k-th
    return *it;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << kthSmallest(a, k) << "\n";
    return 0;
}
7
7

7 again, but the answer is 4. A set keeps each value once: {3 4 7 10 15 20}, the second 4 is gone. (A multiset keeps duplicates but sorts all n values.)

Fix: a max-heap of size k

Q1 turned around: a max-heap of size k holds the k smallest so far; when it grows past k, pop() throws out the biggest. At the end, top() is the biggest of the k smallest: the k-th smallest.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int kthSmallest(const vector<int>& a, int k) {
    priority_queue<int> pq;              // max-heap: the k smallest
    for (int x : a) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();   // drop the biggest
    }
    return pq.top();                     // the biggest of the k smallest
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    cout << kthSmallest(a, k) << "\n";
    return 0;
}
4
7

O(n log k) time, O(k) space.

Another way: nth_element. nth_element(a.begin(), a.begin() + k - 1, a.end()) puts the k-th smallest at index k − 1, smaller-or-equal values before it and bigger-or-equal after, in O(n) on average (it changes the vector):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {7, 10, 4, 3, 20, 15, 4};
    int k = 3;
    nth_element(a.begin(), a.begin() + k - 1, a.end());
    cout << a[k - 1] << "\n";
    return 0;
}
4

Q3: Merge k sorted vectors

Problem. Given k sorted vectors (each as its length m, then m numbers), print one sorted list.

Input Output
1 4 7, 2 5 8, 3 6 9 1 2 3 4 5 6 7 8 9
1 4 7, (empty), 2 5, 0 3 6 9 0 1 2 3 4 5 6 7 9

Think out loud. Only the current front of each list can be next. Edge cases: an empty list, lists of different lengths. Big test (0): 50,000 lists of 20 numbers (1,000,000 in total).

The obvious attempt: scan all k fronts every time

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeK(const vector<vector<int>>& lists) {
    int k = lists.size();
    vector<int> pos(k, 0), all;
    while (true) {
        int best = -1;                   // the list with the smallest front
        for (int i = 0; i < k; i++)
            if (pos[i] < (int)lists[i].size() &&
                (best == -1 || lists[i][pos[i]] < lists[best][pos[best]])) best = i;
        if (best == -1) break;           // every list is used up
        all.push_back(lists[best][pos[best]++]);
    }
    return all;
}

int main() {
    int k;
    cin >> k;
    vector<vector<int>> lists(k);
    for (auto& v : lists) {
        int m;
        cin >> m;
        v.resize(m);
        for (int& x : v) cin >> x;
    }
    if (k == 0) {                        // test: 50,000 lists of 20
        lists.assign(50000, vector<int>(20));
        for (int i = 0; i < 50000; i++)
            for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
    }
    vector<int> all = mergeK(lists);
    if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
    for (int x : all) cout << x << " ";
    cout << "\n";
    return 0;
}
1 2 3 4 5 6 7 8 9 

On the big test:

Time Limit Exceeded

1,000,000 numbers × 50,000 fronts = 50,000,000,000 comparisons: O(N · k), and only one front changed each time.

The idea: the k fronts in a min-heap

The heap holds one entry per list, its current front, as a tuple {value, which list, index in that list} (a tuple groups several values into one; greater<> compares tuples by their first value, then the next). Pop the smallest; push the next value from the same list. The heap has at most k entries, so each step is O(log k).

auto [val, li, idx] = pq.top(); is a structured binding (C++17): it unpacks the tuple into three named variables.

Attempt: push lists[i][0] for every list

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<int> mergeK(const vector<vector<int>>& lists) {
    // {value, which list, index in that list}, smallest value on top
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    for (int i = 0; i < (int)lists.size(); i++)
        pq.push({lists[i][0], i, 0});
    vector<int> all;
    while (!pq.empty()) {
        auto [val, li, idx] = pq.top();
        pq.pop();
        all.push_back(val);
        if (idx + 1 < (int)lists[li].size()) pq.push({lists[li][idx + 1], li, idx + 1});
    }
    return all;
}

int main() {
    int k;
    cin >> k;
    vector<vector<int>> lists(k);
    for (auto& v : lists) {
        int m;
        cin >> m;
        v.resize(m);
        for (int& x : v) cin >> x;
    }
    if (k == 0) {                        // test: 50,000 lists of 20
        lists.assign(50000, vector<int>(20));
        for (int i = 0; i < 50000; i++)
            for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
    }
    vector<int> all = mergeK(lists);
    if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
    for (int x : all) cout << x << " ";
    cout << "\n";
    return 0;
}

On the test with an empty list:

Runtime Error (SIGSEGV)

The second list is empty and lists[1][0] reads an element that doesn't exist. [] never checks the size: undefined behaviour, here a segmentation fault before anything was printed. (lists[1].at(0) would throw std::out_of_range instead.) The scan version compared pos[i] with the size every time, so it never fell for this.

Fix: push only lists that have a front

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<int> mergeK(const vector<vector<int>>& lists) {
    // {value, which list, index in that list}, smallest value on top
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
    for (int i = 0; i < (int)lists.size(); i++)
        if (!lists[i].empty()) pq.push({lists[i][0], i, 0});
    vector<int> all;
    while (!pq.empty()) {
        auto [val, li, idx] = pq.top();
        pq.pop();
        all.push_back(val);
        if (idx + 1 < (int)lists[li].size()) pq.push({lists[li][idx + 1], li, idx + 1});
    }
    return all;
}

int main() {
    int k;
    cin >> k;
    vector<vector<int>> lists(k);
    for (auto& v : lists) {
        int m;
        cin >> m;
        v.resize(m);
        for (int& x : v) cin >> x;
    }
    if (k == 0) {                        // test: 50,000 lists of 20
        lists.assign(50000, vector<int>(20));
        for (int i = 0; i < 50000; i++)
            for (int j = 0; j < 20; j++) lists[i][j] = j * 50000 + i;
    }
    vector<int> all = mergeK(lists);
    if (all.size() > 20) { cout << all.size() << " merged, last " << all.back() << "\n"; return 0; }
    for (int x : all) cout << x << " ";
    cout << "\n";
    return 0;
}
0 1 2 3 4 5 6 7 9 
1 2 3 4 5 6 7 8 9 

The big test, instantly:

1000000 merged, last 999999

O(N log k) time for N numbers in total, O(k) heap space (plus the output).

Complexity summary

Program Time Extra space
k largest, find max + erase k times O(n · k): TLE O(k)
k largest, sort everything O(n log n) O(1)–O(n)
k largest, min-heap of size k O(n log k) O(k)
k-th smallest, set O(n log n), wrong with duplicates O(n)
k-th smallest, max-heap of size k O(n log k) O(k)
k-th smallest, nth_element O(n) average O(1)
merge k lists, scan fronts O(N · k): TLE O(k)
merge k lists, heap of fronts O(N log k) O(k)

Rule of thumb: k largest → min-heap; k smallest → max-heap. The heap's top is the one about to be thrown out.

Common mistakes (and the real results)

Mistake What you see Why Fix
priority_queue<int> for the k largest 3 2 1 pop() drops the biggest greater<int>: a min-heap
greater<int> for the k-th smallest the k-th largest the heap drops the smallest the default max-heap
a set for the k-th smallest 7 instead of 4 duplicates vanish a heap, multiset or nth_element
lists[i][0] for every list Runtime Error (SIGSEGV) an empty list has no [0] if (!lists[i].empty())
find max + erase k times Time Limit Exceeded O(n · k) a heap of size k
pq.top() on an empty heap undefined behaviour nothing to read check pq.empty()
priority_queue<int, greater<int>> compile error the 2nd argument must be the container priority_queue<int, vector<int>, greater<int>>

The last one, for example priority_queue<int, greater<int>> pq; on line 6, gives:

main.cpp: In function 'int main()':
main.cpp:6:36: error: no type named 'value_type' in 'struct std::greater<int>'
    6 |     priority_queue<int, greater<int>> pq;
      |                                    ^~
main.cpp:6:36: error: template argument 3 is invalid
main.cpp:7:8: error: request for member 'push' in 'pq', which is of non-class type 'int'
    7 |     pq.push(3);
      |        ^~~~

Your turn: sort a nearly sorted array (solution)

Problem. Every value is at most k places from its sorted position. Sort it in O(n log k). 6 5 3 2 8 10 9, k = 3 → 2 3 5 6 8 9 10.

Idea. The smallest remaining value is always among the next k + 1 values. Keep a min-heap of k + 1 values: push the next one, and once the heap has k + 1 values, pop the top into the answer.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
        if ((int)pq.size() > k) { cout << pq.top() << " "; pq.pop(); }
    }
    while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
    cout << "\n";
    return 0;
}

Input 7 3 / 6 5 3 2 8 10 9:

2 3 5 6 8 9 10 

Practice questions (with solutions)

1. The k most frequent numbers.

Solution

Count with a map, then keep a min-heap of {count, value} of size k.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; i++) { int x; cin >> x; cnt[x]++; }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;   // {count, value}
    for (auto [value, c] : cnt) {
        pq.push({c, value});
        if ((int)pq.size() > k) pq.pop();
    }
    while (!pq.empty()) {
        cout << pq.top().second << " (x" << pq.top().first << ")\n";
        pq.pop();
    }
    return 0;
}

Input 9 2 / 1 1 1 2 2 3 3 3 3:

1 (x3)
3 (x4)

2. The k closest points to the origin.

Solution

A max-heap of {distance², x, y} of size k: the farthest kept point is on top and is thrown out first. Compare squared distances to stay in integers.

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<tuple<long long, int, int>> pq;   // max-heap by distance²
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        pq.push({1LL * x * x + 1LL * y * y, x, y});
        if ((int)pq.size() > k) pq.pop();
    }
    while (!pq.empty()) {
        auto [d, x, y] = pq.top();
        pq.pop();
        cout << "(" << x << ", " << y << ") d2 = " << d << "\n";
    }
    return 0;
}

Input 4 2 / 3 3 5 -1 -2 4 1 1:

(3, 3) d2 = 18
(1, 1) d2 = 2

3. Running median with two heaps.

Solution

A max-heap low holds the smaller half, a min-heap high the larger half; keep their sizes equal or low one bigger. The median is low.top() (odd count) or the average of both tops.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> low;                                 // smaller half
    priority_queue<int, vector<int>, greater<int>> high;     // larger half
    int x;
    while (cin >> x) {
        if (low.empty() || x <= low.top()) low.push(x); else high.push(x);
        if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); }
        else if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
        if (low.size() > high.size()) cout << low.top() << " ";
        else cout << (low.top() + high.top()) / 2.0 << " ";
    }
    cout << "\n";
    return 0;
}

Input 5 15 1 3 8:

5 10 5 4 5 

Mini project: a hospital emergency queue

Patients arrive with a severity (higher = more urgent); next calls the most urgent, and among equal severity the one who came first. A heap of {severity, -arrival} does both.

#include <iostream>
#include <string>
#include <queue>
#include <tuple>
using namespace std;

int main() {
    priority_queue<tuple<int, int, string>> er;   // {severity, -arrival order, name}
    string cmd;
    int arrival = 0;
    while (cin >> cmd) {
        if (cmd == "arrive") {
            string name;
            int severity;
            cin >> name >> severity;
            er.push({severity, -arrival, name});
            arrival++;
        } else if (er.empty()) {
            cout << "nobody waiting\n";
        } else {
            auto [sev, order, name] = er.top();
            er.pop();
            cout << "now seeing " << name << " (severity " << sev << ")\n";
        }
    }
    return 0;
}
now seeing Meena (severity 5)
now seeing Arjun (severity 5)
now seeing Ravi (severity 2)
now seeing Kavya (severity 1)
nobody waiting

Meena and Arjun both have severity 5; Meena arrived first, so -arrival is larger for her and she is seen first.

Quick quiz

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : {8, 3, 9, 1, 6}) {
        pq.push(x);
        if (pq.size() > 2) pq.pop();
    }
    cout << pq.top() << " " << pq.size() << "\n";
    return 0;
}

(A) 8 2 (B) 1 2 (C) 9 2 (D) 3 2

Answer

(A) 8 2. A min-heap of size 2 keeps the 2 largest values (9 and 8); every pop() threw out the smallest. The top is the smaller of the two, 8.

8 2

Interview questions

  1. What is a heap? A complete binary tree where every parent is ≥ (max-heap) or ≤ (min-heap) its children, usually stored in an array.
  2. Costs of priority_queue? push/pop O(log n), top O(1); building a heap from n values with make_heap is O(n).
  3. How do you make a min-heap in C++? priority_queue<int, vector<int>, greater<int>>, or push negated values into a max-heap.
  4. k largest: min-heap or max-heap? A min-heap of size k: its top is the weakest kept value, the one to throw out.
  5. Why O(n log k) and not O(n log n)? The heap never holds more than k + 1 values.
  6. k-th smallest without a heap? nth_element, O(n) on average (quickselect).
  7. Why does a set give the wrong k-th smallest? It removes duplicates; use a heap, a multiset, or nth_element.
  8. How do you merge k sorted lists? A min-heap of the k fronts {value, list, index}: pop the smallest, push the next from that list. O(N log k).
  9. What does greater<> compare for a tuple? The first element, then the second on a tie, and so on.
  10. Can you change or remove a value in the middle of a priority_queue? No; use a set/multiset, or "lazy deletion" (skip stale entries when they reach the top).

Glossary

Term Meaning Example
Heap A tree kept so the best value is always at the root the largest at the top
Max-heap / min-heap Top is the largest / the smallest priority_queue<int> / greater<int>
priority_queue The C++ heap container adaptor, from <queue> pq.push(5); pq.top();
Comparator The rule that decides the order greater<int>
greater<int> A comparator meaning "a > b", which turns the heap into a min-heap priority_queue<int, vector<int>, greater<int>>
Binary tree A tree where each node has at most two children root 12, children 5 and 11
k largest The k biggest values 5 11 12 from 3 1 5 12 2 11
k-th smallest The value at position k in sorted order, duplicates counted 4 in 3 4 4 7 …
set A sorted container of unique values {3, 4, 7}
multiset A sorted container that keeps duplicates {3, 4, 4, 7}
nth_element Puts the k-th value in its sorted place in O(n) average nth_element(b, b + k - 1, e)
tuple Several values grouped into one {value, list, index}
Structured binding Unpacking a pair or tuple into named variables (C++17) auto [val, li, idx] = pq.top();
Merge k sorted lists Combine k sorted lists into one sorted list 1 4 7 + 2 5 8 → 1 2 4 5 7 8
O(n log k) n steps, each costing log k a heap of size k
Time Limit Exceeded (TLE) The judge stopped a program that ran too long O(n · k) for a million numbers

Summary

  • priority_queue<int> is a max-heap; greater<int> makes a min-heap. push/pop O(log n), top O(1).
  • k largest: a min-heap of size k (throw out the weakest). O(n log k).
  • k-th smallest: a max-heap of size k, top() at the end; duplicates count, so not a set. Or nth_element.
  • Merge k sorted vectors: a min-heap of {value, list, index}; push only non-empty lists. O(N log k).

Next episode: Matrix questions: transpose and rotate a matrix by 90° in place, print it in spiral order, and search a row- and column-sorted matrix with the staircase method.