# K Closest Points to Origin

- **Canonical ID**: `k-closest-points-to-origin`
- **Canonical URL**: https://dsacheatsheet.com/problems/k-closest-points-to-origin
- **Difficulty**: medium
- **Patterns**: Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/k-closest-points-to-origin/

## 1. Core Invariant / The Trick

Maintain a bounded max-heap of size `k` keyed by squared Euclidean distance `x^2 + y^2` (skip `sqrt` to avoid floats). Any larger candidate evicts itself if `len > k` (or Quickselect for O(N) expected time).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N log k)`
- **Space Complexity**: `O(k)`
- **Proof**: Heap size never exceeds k; each of N points triggers at most one O(log k) push/pop.

## 3. Minimal Idiomatic Code

### Python
```python
def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
    h = []
    for i, (x, y) in enumerate(points):
        dist = -(x * x + y * y)
        if len(h) < k:
            heapq.heappush(h, (dist, i, x, y))
        elif dist > h[0][0]:
            heapq.heapreplace(h, (dist, i, x, y))
    return [[x, y] for _, _, x, y in h]
```

### TypeScript
```typescript
export function kClosest(points: number[][], k: number): number[][] {
  const h: Array<[number, number[]]> = [];
  const d = (p: number[]) => p[0] * p[0] + p[1] * p[1];
  const push = (item: [number, number[]]) => {
    h.push(item);
    for (let i = h.length - 1; i > 0; ) {
      const p = (i - 1) >> 1;
      if (h[p][0] >= h[i][0]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  };
  const pop = () => {
    const last = h.pop()!;
    if (h.length) {
      h[0] = last;
      for (let i = 0; ; ) {
        let b = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < h.length && h[l][0] > h[b][0]) b = l;
        if (r < h.length && h[r][0] > h[b][0]) b = r;
        if (b === i) break;
        [h[i], h[b]] = [h[b], h[i]];
        i = b;
      }
    }
  };
  for (const pt of points) {
    const dist = d(pt);
    if (h.length < k) push([dist, pt]);
    else if (dist < h[0][0]) { pop(); push([dist, pt]); }
  }
  return h.map((x) => x[1]);
}
```

### C++
```cpp
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < (int)points.size(); ++i) {
        int d = points[i][0]*points[i][0] + points[i][1]*points[i][1];
        pq.push({d, i});
        if ((int)pq.size() > k) pq.pop();
    }
    vector<vector<int>> res;
    while (!pq.empty()) { res.push_back(points[pq.top().second]); pq.pop(); }
    return res;
}
```

### Java
```java
int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1]));
    for (int[] p : points) {
        pq.offer(p);
        if (pq.size() > k) pq.poll();
    }
    return pq.toArray(new int[k][]);
}
```

### Go
```go
func kClosest(points [][]int, k int) [][]int {
    sort.Slice(points, func(i, j int) bool {
        return points[i][0]*points[i][0]+points[i][1]*points[i][1] <
            points[j][0]*points[j][0]+points[j][1]*points[j][1]
    })
    return points[:k]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Comparing raw `sqrt` floats loses precision and wastes cycles; `x*x + y*y` is strictly monotonic for non-negative distances.
- Using a min-heap instead of max-heap costs O(N log N) instead of O(N log k).

### Follow-ups
- Quickselect partitions points in-place in O(N) average time when k can be large.