NeetCode #531LC-973MediumHeap / Priority QueueNC 150NC 250
← Back to All Problems#531 · #973 · K Closest Points to Origin(最接近原点的 K 个点)
📌 Problem Statement & Constraints
Given an array of points and an integer
k, return the k closest points to the origin, in any order. Constraints: 1 <= k <= points.length <= 10^4, -10^4 <= x, y <= 10^4.💡 Core Algorithmic Approaches
- The distance comparison uses squared distance, avoiding the square root entirely.
- A heap of size
kkeyed by squared distance gives O(n log k), which beats sorting at O(n log n) whenkis small. - For an exact tie-break, include the coordinates in the key so the tuples are comparable.
heapq.nsmallestis a concise way to express the size-kselection.
💻 Benchmark Python3 Implementation
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
import heapq
# squared distance; no need for the square root
return heapq.nsmallest(k, points, key=lambda p: p[0] * p[0] + p[1] * p[1])
# Explicit size-k max-heap: O(n log k) time, O(k) space
class Solution2:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
import heapq
h = [] # max-heap of (-dist, x, y)
for x, y in points:
d = x * x + y * y
heapq.heappush(h, (-d, x, y))
if len(h) > k:
heapq.heappop(h) # evict the farthest
return [[x, y] for _, x, y in h]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log k): each point costs one heap operation on a heap of size at most k.
💾 Space Complexity
O(k) for the bounded heap (or O(n) for nsmallest).
⚠️ Interview Pitfalls & Follow-ups
- Using
math.sqrt: it introduces floating-point error and is unnecessary for comparisons. - Sorting all points: O(n log n), worse than O(n log k) when
kis small. - Keeping a min-heap of all distances: O(n) space and no benefit.
- Forgetting a tie-breaker in the tuple: equal distances would make the tuples compare by
x, which works but is accidental -- including the coordinates makes it explicit and safe.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.