LeetCode 973: K Closest Points to Origin (Max-Heap of Size K)
LeetCode 973HeapGeometryToday we solve LeetCode 973 - K Closest Points to Origin.
Source: https://leetcode.com/problems/k-closest-points-to-origin/
English
Problem Summary
Given points on a 2D plane and an integer k, return any k points with the smallest Euclidean distance to the origin (0,0).
Key Insight
Compare squared distances x*x + y*y (no square root needed). Keep a max-heap of size k so the heap top is the farthest among the current k best points. When a closer point appears, replace the top.
Algorithm
- Initialize empty max-heap by squared distance.
- Iterate all points, compute squared distance.
- Push point to heap.
- If heap size exceeds k, pop one (the current farthest).
- Remaining heap points are the answer.
Complexity Analysis
Let n be number of points.
Time: O(n log k).
Space: O(k).
Common Pitfalls
- Using true distance with sqrt unnecessarily.
- Building a min-heap of all points then popping k, which is O(n log n).
- Overflow risk in some languages if coordinates are larger than 32-bit multiplications.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
for (int[] p : points) {
int d = p[0] * p[0] + p[1] * p[1];
pq.offer(new int[]{d, p[0], p[1]});
if (pq.size() > k) pq.poll();
}
int[][] ans = new int[k][2];
int i = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
ans[i][0] = cur[1];
ans[i][1] = cur[2];
i++;
}
return ans;
}
}import "container/heap"
type Node struct {
d, x, y int
}
type MaxHeap []Node
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].d > h[j].d }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(v interface{}) { *h = append(*h, v.(Node)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
v := old[n-1]
*h = old[:n-1]
return v
}
func kClosest(points [][]int, k int) [][]int {
h := &MaxHeap{}
heap.Init(h)
for _, p := range points {
d := p[0]*p[0] + p[1]*p[1]
heap.Push(h, Node{d: d, x: p[0], y: p[1]})
if h.Len() > k {
heap.Pop(h)
}
}
ans := make([][]int, 0, k)
for h.Len() > 0 {
cur := heap.Pop(h).(Node)
ans = append(ans, []int{cur.x, cur.y})
}
return ans
}class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
using T = array<int, 3>; // {dist, x, y}
priority_queue<T> pq;
for (auto& p : points) {
int d = p[0] * p[0] + p[1] * p[1];
pq.push({d, p[0], p[1]});
if ((int)pq.size() > k) pq.pop();
}
vector<vector<int>> ans;
ans.reserve(k);
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
ans.push_back({cur[1], cur[2]});
}
return ans;
}
};from typing import List
import heapq
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = [] # max-heap by storing (-dist, x, y)
for x, y in points:
dist = x * x + y * y
heapq.heappush(heap, (-dist, x, y))
if len(heap) > k:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]var kClosest = function(points, k) {
class MaxHeap {
constructor() { this.a = []; }
size() { return this.a.length; }
top() { return this.a[0]; }
push(v) {
this.a.push(v);
this._up(this.a.length - 1);
}
pop() {
const n = this.a.length;
if (n === 1) return this.a.pop();
const top = this.a[0];
this.a[0] = this.a.pop();
this._down(0);
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p][0] >= this.a[i][0]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
_down(i) {
const n = this.a.length;
while (true) {
let m = i, l = i * 2 + 1, r = i * 2 + 2;
if (l < n && this.a[l][0] > this.a[m][0]) m = l;
if (r < n && this.a[r][0] > this.a[m][0]) m = r;
if (m === i) break;
[this.a[m], this.a[i]] = [this.a[i], this.a[m]];
i = m;
}
}
}
const heap = new MaxHeap();
for (const [x, y] of points) {
const d = x * x + y * y;
heap.push([d, x, y]);
if (heap.size() > k) heap.pop();
}
const ans = [];
while (heap.size() > 0) {
const [, x, y] = heap.pop();
ans.push([x, y]);
}
return ans;
};中文
题目概述
给定二维平面上的点集和整数 k，返回距离原点 (0,0) 最近的任意 k 个点。
核心思路
比较平方距离 x*x + y*y 即可，不需要开根号。维护一个大小最多为 k 的大顶堆，堆顶表示当前 k 个候选里最远的点。遇到更近的点就替换堆顶。
算法步骤
- 初始化一个按“距离降序”的大顶堆。
- 遍历每个点，计算平方距离并入堆。
- 若堆大小超过 k，弹出堆顶（当前最远点）。
- 遍历结束后，堆中剩下的就是答案。
复杂度分析
设点数量为 n。
时间复杂度：O(n log k)。
空间复杂度：O(k)。
常见陷阱
- 用真实欧氏距离并调用 sqrt，会带来不必要开销。
- 先把全部点放入最小堆再弹出 k 个，复杂度退化到 O(n log n)。
- 某些语言中坐标平方可能溢出，需留意整数范围。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
for (int[] p : points) {
int d = p[0] * p[0] + p[1] * p[1];
pq.offer(new int[]{d, p[0], p[1]});
if (pq.size() > k) pq.poll();
}
int[][] ans = new int[k][2];
int i = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
ans[i][0] = cur[1];
ans[i][1] = cur[2];
i++;
}
return ans;
}
}import "container/heap"
type Node struct {
d, x, y int
}
type MaxHeap []Node
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].d > h[j].d }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(v interface{}) { *h = append(*h, v.(Node)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
v := old[n-1]
*h = old[:n-1]
return v
}
func kClosest(points [][]int, k int) [][]int {
h := &MaxHeap{}
heap.Init(h)
for _, p := range points {
d := p[0]*p[0] + p[1]*p[1]
heap.Push(h, Node{d: d, x: p[0], y: p[1]})
if h.Len() > k {
heap.Pop(h)
}
}
ans := make([][]int, 0, k)
for h.Len() > 0 {
cur := heap.Pop(h).(Node)
ans = append(ans, []int{cur.x, cur.y})
}
return ans
}class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
using T = array<int, 3>; // {dist, x, y}
priority_queue<T> pq;
for (auto& p : points) {
int d = p[0] * p[0] + p[1] * p[1];
pq.push({d, p[0], p[1]});
if ((int)pq.size() > k) pq.pop();
}
vector<vector<int>> ans;
ans.reserve(k);
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
ans.push_back({cur[1], cur[2]});
}
return ans;
}
};from typing import List
import heapq
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = [] # max-heap by storing (-dist, x, y)
for x, y in points:
dist = x * x + y * y
heapq.heappush(heap, (-dist, x, y))
if len(heap) > k:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]var kClosest = function(points, k) {
class MaxHeap {
constructor() { this.a = []; }
size() { return this.a.length; }
top() { return this.a[0]; }
push(v) {
this.a.push(v);
this._up(this.a.length - 1);
}
pop() {
const n = this.a.length;
if (n === 1) return this.a.pop();
const top = this.a[0];
this.a[0] = this.a.pop();
this._down(0);
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p][0] >= this.a[i][0]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
_down(i) {
const n = this.a.length;
while (true) {
let m = i, l = i * 2 + 1, r = i * 2 + 2;
if (l < n && this.a[l][0] > this.a[m][0]) m = l;
if (r < n && this.a[r][0] > this.a[m][0]) m = r;
if (m === i) break;
[this.a[m], this.a[i]] = [this.a[i], this.a[m]];
i = m;
}
}
}
const heap = new MaxHeap();
for (const [x, y] of points) {
const d = x * x + y * y;
heap.push([d, x, y]);
if (heap.size() > k) heap.pop();
}
const ans = [];
while (heap.size() > 0) {
const [, x, y] = heap.pop();
ans.push([x, y]);
}
return ans;
};
Comments