K Closest Points to Origin

Given an array of points[i] = [xi, yi], return the k closest points to the origin (0, 0) using Euclidean distance.

Practice Link

Intuition#

We want to keep the k smallest distances at all times. A max-heap of size k does exactly this:

• Push each point's distance onto the heap.
• If the heap grows beyond k, pop the maximum — it's farther than any of the k points currently in the heap, so it can never be an answer.
• After all points are processed, the heap holds exactly the k closest.

Why skip sqrt? Distance comparisons don't need the actual distance value — just relative order. Since sqrt is monotonically increasing, d₁ < d₂ ⟺ d₁² < d₂². Comparing squared distances avoids floating-point precision loss and is faster.

Solution — Max-Heap of Size k#

typedef pair<int, vector<int>> pvi;

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int n = points.size();
        priority_queue<pvi> pq;  // max-heap: farthest point on top

        for (int i = 0; i < n; i++) {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            pq.push({dist, {points[i][0], points[i][1]}});

            if (pq.size() > k)
                pq.pop();  // evict the farthest point seen so far
        }

        vector<vector<int>> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

Time Complexity: O(n log k) — each push/pop on a heap of size k costs O(log k)
Space Complexity: O(k) — heap holds at most k+1 elements at a time

Trace — points = [[1,3],[-2,2]], k = 1#

Result: [[-2,2]] ✓

Comparison with other approaches#

The max-heap of size k is the sweet spot for interviews — easy to code, optimal when k is small relative to n.

Common pitfalls#

1. Using sqrt and storing in int
sqrt returns double; truncating to int collapses geometrically different distances to the same integer. Points (1,1) (dist ≈ 1.41) and (1,0) (dist = 1.0) both become 1, breaking heap order. Use squared distance directly.

2. Typo: x*x + x*x instead of x*x + y*y
Computes 2x² — the y-coordinate is ignored entirely. Always double-check both coordinates when computing Euclidean distance.