Skip to content

Volume ITechnology

4.17.3 — K Closest Points to Origin ​

LeetCode 973 · Medium

The problem ​

Return the k points closest to the origin. Any order is fine.

points = [[1,3],[-2,2]], k = 1   →  [[-2,2]]

The distance from a point (x, y) to the origin (0, 0) is \sqrt{x^2 + y^2}, read "the square root of x squared plus y squared". This comes from Pythagoras' theorem: the point, the origin and the spot (x, 0) form a right-angled triangle whose two short sides are x and y long.

points = [[3, 3], [5, -1], [-2, 4]], k = 2   →  [[3, 3], [-2, 4]]

There are up to 10,000 points, and the answer is guaranteed to be unique.

What the problem is really asking ​

This is "keep the k best items" again, like 4.17.1, except that "best" now means smallest distance, and the distance must be worked out from two numbers.

The brute force, and where it wastes work ​

Work out every distance, sort all the points by it, and take the first k.

python
def kClosest(points, k):
    return sorted(points, key=lambda p: p[0] ** 2 + p[1] ** 2)[:k]

That is O(n \log n), and a perfectly fine first answer.

The waste in one sentence: it puts every point in exact order, when we only need to know which k points are closest.

The pattern ​

Two decisions, and the first one is free.

Do not take the square root. Distance is \sqrt{x^2 + y^2}, but you are only comparing distances, and the square root is monotonic — it preserves order. So compare x^2 + y^2 directly. That avoids a floating-point operation per point and, more importantly, avoids floating-point rounding making two genuinely different distances compare equal.

Comparing squared distances instead of distances is a habit worth having, and it appears anywhere geometry meets sorting.

Think of it like comparing the area of two square fields to see which is larger. If one has an area of 16 and another has an area of 25, you don't need to calculate their exact side lengths (4 and 5) to know the second field is bigger. Skipping the square root saves calculating the side length!

Then: a size-k heap. You want the k smallest distances, so the item you evict is the largest of the ones you are keeping — which means a max-heap.

Note the flip from 4.17.1, where you wanted the k largest and used a min-heap. The rule is the same in both:

The root must be the item you are about to throw away.

k largest → min-heap. k smallest → max-heap.

The solution ​

python
import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []                                        # (1) max-heap via negation

        for x, y in points:  # (2)
            d = x * x + y * y                            # (3) no square root
            heapq.heappush(heap, (-d, x, y))  # (4)
            if len(heap) > k:  # (5)
                heapq.heappop(heap)                      # drop the farthest

        return [[x, y] for _, x, y in heap]  # (6)
ts
function kClosest(points: number[][], k: number): number[][] {
  // TypeScript has no built-in heap. MaxHeap is the heap from 4.16, here
  // ordered by squared distance, so pop() removes the farthest point.
  const heap = new MaxHeap<number[]>((p) => p[0] * p[0] + p[1] * p[1]);  // (1)
  for (const p of points) {  // (2)
    heap.push(p);  // (4)
    if (heap.size > k) heap.pop();  // (5)
  }
  return heap.toArray();  // (6)
}

Line by line ​

(1) An empty heap. Python's heapq keeps the smallest item at the front. We want the farthest of the kept points at the front, because that is the one a closer point should replace. So we store each distance as a negative number. The farthest point has the most negative entry, so it sits at the front.

(2) Visit every point once.

(3) The squared distance. We skip the square root. Square root keeps order: if one squared distance is bigger, so is the real distance. So comparing squared distances gives the same answer. It also avoids decimals, which can round two different distances to look equal.

(4) Push the point, as a group of three: the negated distance first, so the heap orders by distance, then x and y.

(5) Too many points? Remove the front, which is the farthest of the k + 1. It can never be among the k closest, because k closer points are already known.

(6) What is left are the k closest points. We drop the stored distance and return [x, y] pairs.

Trace ​

Take points = [[3, 3], [5, -1], [-2, 4]] and k = 2. Squared distances: 18, 26 and 20.

PointSquared distanceHeap after push (distances)Too many?Heap after
[3, 3]18no
[5, −1]26no
[−2, 4]20yes, remove the farthest, 26

The answer is [[3, 3], [-2, 4]].

Negating the distance turns Python's min-heap into a max-heap, so the root is the farthest of the k kept so far — exactly the one a closer point should replace.

Complexity ​

O(n \log k) time, O(k) space.

Let's break this down:

  • Time Complexity: We iterate through all n points. For each point, pushing to a heap of size k takes O(\log k) time. Popping also takes O(\log k) time. So n points \times O(\log k) operations gives O(n \log k). The squared distance calculation is just O(1).
  • Space Complexity: We maintain a heap of at most k elements, so it uses O(k) extra memory.

Edge cases ​

  • k equals the number of points. Nothing is ever removed, and every point is returned.
  • Points at the same distance, like [1, 0] and [0, 1]. The problem promises the answer is unique, so a tie never decides who is in or out.
  • Negative coordinates. Squaring removes the sign, so (-2)^2 = 4, the same as 2^2.

The three solutions, and how to choose ​

Sort by distance and take the first k — O(n \log n), three lines, and completely acceptable:

python
return sorted(points, key=lambda p: p[0]**2 + p[1]**2)[:k]

Say this first. It is correct and it establishes the squared-distance point immediately.

Size-k heap — O(n \log k), and it works on a stream, since it never needs all the points at once.

Quickselect — O(n) on average. Partition around a pivot as in quicksort, but recurse into only the side containing the k-th position. After partitioning, the first k elements are the k closest, in no particular order — which is all the problem asks for.

Quickselect's worst case is O(n^2) if pivots are chosen badly, fixed in practice by choosing a random pivot. It also reorders the input.

timespaceworks on a stream
sortO(n \log n)O(n)no
size-k heapO(n \log k)O(k)yes
quickselectO(n) averageO(1)no

The interview answer is to name all three and the condition that picks each. If they push for the best asymptotic time, quickselect. If they mention a stream or limited memory, the heap.

Quickselect, briefly ​

python
def kClosest(self, points, k):
    def dist(p): return p[0]**2 + p[1]**2

    def partition(lo, hi) -> int:
        pivot = dist(points[hi])
        store = lo
        for i in range(lo, hi):
            if dist(points[i]) < pivot:
                points[store], points[i] = points[i], points[store]
                store += 1
        points[store], points[hi] = points[hi], points[store]
        return store

    lo, hi = 0, len(points) - 1
    while lo < hi:
        p = partition(lo, hi)
        if p == k: break
        if p < k: lo = p + 1
        else: hi = p - 1

    return points[:k]

Why it is O(n) on average: the first partition costs n, the second costs about n/2, then n/4, and so on. That sum is bounded by 2n. Contrast quicksort, which recurses into both halves and pays O(n) per level across \log n levels.

Randomising the pivot before partitioning is what keeps the average case honest on sorted or adversarial input.

Where this goes next ​

  • Kth Largest Element in an Array — the same three solutions on plain numbers. 4.17.4.
  • Top K Frequent Elements — same again, over counts, with a bucket-sort option because frequencies are bounded. 4.4.5.
  • Nearest neighbour search at scale — a k-d tree or a locality-sensitive hash, because a linear scan over billions of points is too slow no matter which selection method follows it.

What the interviewer will push on ​

"Why no square root?" It is monotonic, so it does not change the ordering, and skipping it avoids floating-point error and work.

"Max-heap or min-heap?" Max-heap for the k smallest — the root is what you evict.

"Can you do better than O(n \log k)?" Quickselect, O(n) average, and say why: the partition sizes halve, summing to 2n.

"What if the points arrive as a stream?" Only the heap survives; quickselect needs the whole array.

"What if k is 1?" A single linear scan for the minimum. The general machinery collapses to something much simpler.

One thing to volunteer: state the squared-distance point before writing anything. It is a small thing that immediately signals you have thought about the geometry rather than copied a template.

Next: 4.17.4 Kth Largest Element in an Array — the same selection question, stripped to its simplest form.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet