Heap & Priority Queue

Intuition 1: Sort — O(n log n)

Sort descending, return index k-1. Simple but doesn't use heap efficiently.

Intuition 1: Level-order BFS + min-heap of size k

Level-order traversal to compute sum of each level. Maintain a min-heap of size k over those level sums. Same pattern as kth largest — min-heap of size k, root = kth largest.

Intuition 1: Two heaps — lower half max-heap, upper half min-heap

Split stream into lower half (max-heap) and upper half (min-heap). Invariant: lower.size() === upper.size() OR lower.size() === upper.size() + 1. AddNum: always push to lower first, then rebalance. Pop from lower into upper. If upper becomes bigger, pop from upper into lower. FindMedian: if sizes equal → (lower.top + upper.top) / 2. If lower bigger → lower.top.

Intuition 1: Build frequency map, heap on frequencies

Count frequencies with a hashmap. Then maintain a min-heap of size k keyed by frequency. After processing all elements, the heap contains the k most frequent elements.

Intuition 1: Sort by squared distance — O(n log n)

Compute x²+y² (no sqrt needed — monotone). Sort ascending. Return first k. Simple but processes all n points.

Intuition 1: O(kN) brute force — merge lists one by one

Merge lists[0] and lists[1], then merge result with lists[2], etc. Each merge is O(N) total, done k-1 times = O(kN).

Intuition 1: Sort on every query — O(n log n) per query

Store all numbers. On findMedian, sort and return middle. Too slow for large streams.

Intuition 1: Greedy with two heaps — min-heap by capital, max-heap by profit

Greedy: at each step, pick the highest-profit project we can afford. Use a min-heap sorted by required capital (to find newly affordable projects) and a max-heap by profit (to pick the best among affordable ones). For each of k rounds: move all newly affordable projects to max-heap, pick the max-profit one.