Heaps, Top-K & Intervals: Deriving the Optimal Solution for 5 Problems (LC 215/347/23/56/253)

This post drills two high-frequency interview weapons at once:

• Heap (priority queue): whenever you see "top K / bottom K / the Kth / merge K ways / dynamic extremes," a heap is the first thought — it maintains a "rolling set of extremes" in O(log k).
• Intervals: whenever you see "merge / overlap / scheduling," it's almost always sort by start (or endpoint) first, then sweep linearly.

Continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Kth largest (215) → top-K frequent (347) → merge K sorted lists (23) → merge intervals (56) → minimum meeting rooms (253)

① LC 215 — Kth Largest Element in an Array

📋 Problem: Given an integer array nums and integer k, return the kth largest element (kth largest in sorted order, not the kth distinct).

Example: nums = [3,2,1,5,6,4], k = 2 → 5; [3,2,3,1,2,4,5,5,6], k = 4 → 4

🧭 From reading the problem to the solution

1. Break it down: you want the kth largest, but you don't need a full sort — only the top k matter.
2. Brute force: sort and take the kth from the end, O(n log n). Works, but does extra work.
3. Key insight (size-k min-heap): keep a min-heap of size k; push each element, and pop the smallest when size exceeds k. What remains is "the k largest," and the heap top (the smallest of them) is the kth largest.
4. Optimum: min-heap, O(n log k). Faster than sorting (especially for small k).

import heapq

def findKthLargest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)        # drop the smallest, keep k largest
    return heap[0]                      # smallest of the k largest = kth largest

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;   // min-heap
    for (int n : nums) {
        heap.push(n);
        if ((int)heap.size() > k) heap.pop();
    }
    return heap.top();
}

• Complexity: O(n log k) time, O(k) space.
• Pitfall: ① use a min-heap to hold "the k largest" (counterintuitive but correct); ② the advanced answer is Quickselect, O(n) average / O(n²) worst — say it for bonus points; ③ the heap solution shines on streaming data (elements keep arriving, kth largest on demand).

② LC 347 — Top K Frequent Elements

📋 Problem: Given an integer array nums and integer k, return the k most frequent elements (any order).

Example: nums = [1,1,1,2,2,3], k = 2 → [1,2]; [1], k = 1 → [1]

🧭 From reading the problem to the solution

1. Break it down: compute each value's frequency (HashMap), and the problem becomes "top-K over frequencies" — the 215 trick again.
2. Brute force: sort all (value, freq) pairs and take the top k, O(n log n).
3. Key insight (heap or bucket): ① a size-k min-heap over frequencies, O(n log k); ② better still, bucket sort: frequency maxes out at n, so make n+1 buckets, drop values into "the bucket for their frequency," and collect k from the highest frequency down — O(n).
4. Optimum: heap is easy; bucket is fastest.

import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)   # O(n log k)

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    for (auto& [num, freq] : count) {
        heap.push({freq, num});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> res;
    while (!heap.empty()) { res.push_back(heap.top().second); heap.pop(); }
    return res;
}

💡 Advanced: O(n) bucket sort (frequency as index)

from collections import Counter
def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for freq in range(len(buckets) - 1, 0, -1):     # high freq → low
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res

• Complexity: heap O(n log k), bucket O(n); O(n) space.
• Pitfall: ① frequencies range 1..n, so n+1 buckets fit exactly; ② the problem guarantees a unique answer, so no tie worries; ③ the heap holds (freq, value), compared by frequency.

③ LC 23 — Merge k Sorted Lists

📋 Problem: Given k sorted linked lists, merge them into one sorted list and return it.

Example: lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]

🧭 From reading the problem to the solution

1. Break it down: each step picks the smallest among the current heads of the k lists — a "k-way merge."
2. Brute force: dump all into an array, sort, rebuild, O(N log N) (N total nodes) — ignores that each list is sorted.
3. Key insight (size-k min-heap): put the k heads in a min-heap; pop the smallest onto the result tail, then push its next node. The heap holds at most k, each pop O(log k).
4. Optimum: min-heap, O(N log k). (Alt: pairwise divide-and-conquer, same complexity.)

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i breaks val ties
    dummy = tail = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* node : lists) if (node) heap.push(node);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node; tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

• Complexity: O(N log k) time, O(k) space.
• Pitfall: ① Python compares tuples, but ListNode isn't comparable — push a unique i as a tiebreaker, or equal vals throw; ② a dummy head simplifies linking; ③ only push back when node.next exists.

④ LC 56 — Merge Intervals

📋 Problem: Given an array of intervals (each [start, end]), merge all overlapping intervals and return the non-overlapping set.

Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]; [[1,4],[4,5]] → [[1,5]]

🧭 From reading the problem to the solution

1. Break it down: deciding which intervals overlap is hard if they're unordered. Sort first, and overlapping ones become adjacent.
2. Key insight (sort by start + sweep): after sorting by start, just compare "the current start" with "the last merged interval's end": if start <= last end, they overlap — extend the last end to the larger of the two; otherwise start a new interval.
3. Why only compare with the last after sorting? Because after sorting, if the current interval overlaps any earlier one, it must also overlap "the last merged one" — transitivity guarantees the last is enough.
4. Optimum: sort + one linear sweep.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])             # sort by start
    res = []
    for start, end in intervals:
        if res and start <= res[-1][1]:            # overlaps the last merged
            res[-1][1] = max(res[-1][1], end)      # extend the end
        else:
            res.append([start, end])
    return res

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());      // sort by start
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (!res.empty() && iv[0] <= res.back()[1])
            res.back()[1] = max(res.back()[1], iv[1]);
        else
            res.push_back(iv);
    }
    return res;
}

• Complexity: O(n log n) time (sort dominates), O(n) space.
• Pitfall: ① sort by start first; ② extend the end with max — handles "nested intervals" like [1,10] containing [2,3], don't blindly overwrite; ③ start <= end vs < depends on whether "just touching" counts as overlap (here it does).

⑤ LC 253 — Meeting Rooms II

📋 Problem: Given meeting times intervals ([start, end]), return the minimum number of meeting rooms required (meetings overlapping in time need separate rooms).

Example: [[0,30],[5,10],[15,20]] → 2; [[7,10],[2,4]] → 1

🧭 From reading the problem to the solution

1. Break it down: the answer = the maximum number of concurrent meetings at any instant (peak concurrency).
2. Brute force: count active meetings at every time point — too slow.
3. Key insight (sort + min-heap of end times): sort by start and process meetings in order. Keep a min-heap of "end times of ongoing meetings." For a new meeting, if the heap top (earliest-ending meeting) <= the new start, that room freed up — pop (reuse the room); then push the new meeting's end. The heap size = rooms in use right now.
4. Optimum: since each step pops at most one and always pushes one, the heap size never shrinks, so the final heap size = peak concurrency = the answer.

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])             # by start
    heap = []                                      # end times of ongoing meetings
    for start, end in intervals:
        if heap and heap[0] <= start:              # earliest meeting freed a room
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());      // by start
    priority_queue<int, vector<int>, greater<int>> heap;  // min-heap of end times
    for (auto& iv : intervals) {
        if (!heap.empty() && heap.top() <= iv[0]) heap.pop();
        heap.push(iv[1]);
    }
    return heap.size();
}

• Complexity: O(n log n) time, O(n) space.
• Pitfall: ① the heap holds end times, top = earliest-ending meeting; ② since the heap size is non-decreasing, the final size is the answer — no need to track a separate max; ③ boundary: a room frees only when end <= start (one meeting can start the instant another ends, per the problem's definition). Alt: split all starts and ends, sort each, and sweep with two pointers (chronological ordering), also O(n log n).

One Table to Remember It All

Pattern-Recognition Cheats

• "Kth largest/smallest, top-K, merge K ways, streaming extremes" → heap (the size-k min-heap is the universal template).
• "top-K by frequency" → heap or bucket sort (bucket is O(n), fastest).
• "merge K sorted structures" → min-heap k-way merge.
• "intervals: overlap / merge / insert" → sort by start then sweep.
• "intervals: max concurrent / minimum resources (rooms/platforms)" → sort + min-heap of end times (peak concurrency).

Two lines to close: "For top-K or merging K ways, use a heap; for intervals, sort then sweep." Recognize these two patterns and this family goes from "head-scratcher" to "template-filling."