⚡Flashcard Drill➔
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

  1. The distance comparison uses squared distance, avoiding the square root entirely.
  2. A heap of size k keyed by squared distance gives O(n log k), which beats sorting at O(n log n) when k is small.
  3. For an exact tie-break, include the coordinates in the key so the tuples are comparable.
  4. heapq.nsmallest is a concise way to express the size-k selection.

💻 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 k is 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems