A warehouse dispatch overlay is given map pins for depots and asked for the k nearest to HQ at (0, 0). The intern version sorted every pin by Euclidean distance and sliced the first k. A city with a dozen depots painted instantly. A national network with tens of thousands of pins was still ranking depots the dispatcher would never send a truck to.

K Closest Points to Origin asks for the k points nearest (0, 0). A heap of size k already keeps the current winners. Sorting every pin uses that answer and still ranks depots you will throw away.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Here we want the opposite polarity: a max-heap on distance so the root is the farthest of the current k — poll it when size > k.

The problem

Given an int[][] points of [x, y] pairs and an int k, return the k points closest to the origin (0, 0). Distance is Euclidean; order of the k answers does not matter. Assume k is at least 1 and at most points.length.

points = [[6, 8], [2, 1], [0, 4], [1, 0]], k = 2  →  [[2, 1], [1, 0]]
points = [[3, 4], [0, -7]],                 k = 1  →  [[3, 4]]
points = [[5, 12], [-9, 0]],                k = 2  →  [[5, 12], [-9, 0]]

First row: squared distances 100, 5, 16, 1 — the two nearest win. Second: 25 beats 49. Third: k equals n, so both pins come back. Return the points themselves, not the distances.

Note: You do not need Math.sqrt. Ranking only needs order, and x² + y² preserves it for non-negative squares. Multiply in long so two large int coordinates cannot overflow the compare.

Sort every point by distance is the honest brute force

Sort the array by squared distance, then copy the first k rows. Correct, and slow in n when k is tiny. Do not sort by x then y — closest to origin is not “smallest x.”

int[][] kClosestSort(int[][] points, int k) {
    Arrays.sort(points, (a, b) -> Long.compare(
            (long) a[0] * a[0] + (long) a[1] * a[1],
            (long) b[0] * b[0] + (long) b[1] * b[1]));
    return Arrays.copyOf(points, k);
}

At a dozen pins this is a rounding error. At tens of thousands you paid O(n log n) to rank every depot, including ones the truck will never visit: which k pins won? A size-k heap ranks only against the current farthest winner.

Note: Arrays.sort mutates points. Fine for a throwaway brute. The heap walk leaves input order alone and still returns the winners.

Size-k max-heap: offer, maybe poll the farthest

Walk each point. The heap is a max-heap on squared distance, not on x or y. Root is the farthest pin you are currently keeping.

  • Offer the point.
  • If the heap now holds more than k points, poll. That poll drops the farthest, so the remaining k are still the closest seen so far.

You never sort the whole list. You never keep the far depots. A pin farther than the current root still gets offered, then immediately polled.

k = 2

offer [6, 8]   d=100   heap [[6, 8]]
offer [2, 1]   d=5     heap [[6, 8], [2, 1]]          root=[6, 8]
offer [0, 4]   d=16    heap [[6, 8], [2, 1], [0, 4]]  size 3 > 2, poll [6, 8]
                       heap [[0, 4], [2, 1]]          root=[0, 4]
offer [1, 0]   d=1     heap [[0, 4], [2, 1], [1, 0]]  size 3 > 2, poll [0, 4]
                       heap [[2, 1], [1, 0]]

answer [[2, 1], [1, 0]]   (order does not matter)

[6, 8] left first, then [0, 4]. The Java is that walk. Reverse Long.compare so the larger squared distance sits at the root — default PriorityQueue order would keep the k farthest:

int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> Long.compare(
                    (long) b[0] * b[0] + (long) b[1] * b[1],
                    (long) a[0] * a[0] + (long) a[1] * a[1]));
    for (int[] p : points) {
        heap.offer(p);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    int[][] answer = new int[k][];
    for (int i = 0; i < k; i++) {
        answer[i] = heap.poll();
    }
    return answer;
}

Time is O(n log k) — one offer (and maybe a poll) per point. Space is O(k) — the heap holds at most k + 1 points. Sort-all is O(n log n) and ranks losers. Do not re-lecture sift at the whiteboard unless they ask.

If k is close to n, sort-all can be simpler to write; the heap still wins when k is tiny next to n.

Note: A min-heap of size k on distance keeps the k farthest. Root is the nearest of that set; polling it throws away a winner. Same size-k shape as Kth Largest in a Stream, inverted polarity: that min-heap peeks the floor of the k largest; this max-heap peeks the farthest of the k closest.

Note: Do not store only the distances. You have to return the points. The comparator reads x and y; the heap holds the int[] rows. Drain in any order — the prompt does not rank the k answers among themselves.

What interviewers usually poke next

  • k = 1. One scan. Track the point with the smallest squared distance. A heap of size 1 is the same idea with extra ceremony; say you noticed.
  • k = n. Return every point. The heap never evicts; copying the input is enough.
  • Ties. If several points sit at the boundary distance, any of the tied points is fine unless they ask for a specific tie-break.
  • Quickselect. Partition on squared distance, average O(n), no heap. Mention it; do not implement unless they ask. The heap is the usual board default when they said “heap” or k is tiny next to n.
  • Why not sqrt. sqrt is strictly increasing on [0, ∞), so it cannot change the ranking. It is wasted work and invites float noise.
  • One-shot kth on values. Kth Largest Element in an Array is the frozen size-k cousin on value, not distance. Do not solve it here.
  • A stream of pins. If depots arrive one at a time with k fixed, the same max-heap survives across arrivals — inverted polarity of Kth Largest in a Stream. This prompt is one-shot.

You are done with this problem when you can say, out loud, why sorting every pin is correct, why a size-k max-heap’s root is the farthest of the current winners, and why a min-heap of size k would keep the wrong k.