2Brute2Best
🔥0
03

Closest / distance (Heap — Top K Sub-pattern)

The rank is a distance to some target. Score each item, then keep the K smallest scores with a max-heap.

Signals in the problem statement
  • ›

    "k closest points to the origin"

  • ›

    "k closest elements to x"

What makes it different

K Closest Points is the template: score = x² + y², no square root needed. Find K Closest Elements gets a sorted array, and that changes everything: the answer is a contiguous window, so binary search for its left edge beats any heap. Ties go to the smaller value.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    K Closest Points to Origin
    Basic Anchor·LeetCode #973
    Medium
  2. 2
    Find K Closest Elements
    Slight Variation·LeetCode #658
    Medium

Template

k-closest-template.cpp
// K closest points to the origin: a MAX-heap of size k keyed on squared distance.
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<pair<long long, int>> pq;                // (dist^2, index); top = farthest kept
    for (int i = 0; i < (int)points.size(); i++) {
        long long d = 1LL * points[i][0] * points[i][0] + 1LL * points[i][1] * points[i][1];
        pq.push({d, i});
        if ((int)pq.size() > k) pq.pop();                   // kick out the farthest
    }
    vector<vector<int>> out;
    while (!pq.empty()) { out.push_back(points[pq.top().second]); pq.pop(); }
    return out;
}
Remember this · Heap — Top K
Trigger
"K largest / smallest / most frequent / closest", kth element, streaming top-K.
Think
Do I really need everything sorted, or only the best K?
Key question
Min-heap or max-heap of size K — which one lets me kick out the worst candidate?
Top K by frequencyStreaming / dynamic