973. K Closest Points to Origin (Medium)

Problem

Given an array points where points[i] = [xᵢ, yᵢ], return the k points closest to the origin (0, 0). The distance metric is Euclidean; squared distance is sufficient for ranking (no need for sqrt).

Example

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

LeetCode 973 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort by squared distance

Sort all points; take the first k.

def k_closest(points, k):
    return sorted(points, key=lambda p: p[0] ** 2 + p[1] ** 2)[:k]  # L1: O(n log n)

function kClosest(points: number[][], k: number): number[][] {
    return [...points]
        .sort((a, b) => (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]))  // L1: O(n log n)
        .slice(0, k);
}

import "sort"

func kClosest(points [][]int, k int) [][]int {
    sort.Slice(points, func(i, j int) bool { // L1: O(n log n)
        di := points[i][0]*points[i][0] + points[i][1]*points[i][1]
        dj := points[j][0]*points[j][0] + points[j][1]*points[j][1]
        return di < dj
    })
    return points[:k]
}

final class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] { Array(points.sorted(by: isCloser).prefix(k)) }
    private func isCloser(_ a: [Int], _ b: [Int]) -> Bool { let da = a[0] * a[0] + a[1] * a[1]; let db = b[0] * b[0] + b[1] * b[1]; return da == db ? (a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]) : da < db }
}

Where the time goes, line by line

Variables: n = number of points, k = number of closest points to return.

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates

Complexity

Time: $O(n log n)$ , driven by L1.
Space: $O(n)$ .

Simple and often accepted.

Approach 2: Size-K max-heap

Keep a max-heap of size K. Each new point is pushed; if the heap exceeds K, pop the farthest.

import heapq

def k_closest(points, k):
    # Max-heap via negated distance
    heap = []
    for x, y in points:                       # L1: iterate n points
        d = -(x * x + y * y)
        if len(heap) < k:
            heapq.heappush(heap, (d, x, y))   # L2: O(log k) push
        elif d > heap[0][0]:
            heapq.heapreplace(heap, (d, x, y)) # L3: O(log k) replace farthest
    return [[x, y] for _, x, y in heap]

// Max-heap on (negated distance, x, y)
type Entry = [number, number, number];

class MaxHeap {
    private data: Entry[] = [];
    get size(): number { return this.data.length; }
    get top(): Entry { return this.data[0]; }
    push(val: Entry): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    // Replace top with val (like heapreplace)
    replace(val: Entry): void {
        this.data[0] = val;
        this._siftDown(0);
    }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p][0] >= this.data[i][0]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let largest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l][0] > this.data[largest][0]) largest = l;
            if (r < n && this.data[r][0] > this.data[largest][0]) largest = r;
            if (largest === i) break;
            [this.data[largest], this.data[i]] = [this.data[i], this.data[largest]]; i = largest;
        }
    }
    entries(): Entry[] { return (this as any).data; }
}

function kClosest(points: number[][], k: number): number[][] {
    const heap = new MaxHeap();
    for (const [x, y] of points) {             // L1: iterate n points
        const d = -(x * x + y * y);
        if (heap.size < k) {
            heap.push([d, x, y]);              // L2: O(log k) push
        } else if (d > heap.top[0]) {
            heap.replace([d, x, y]);           // L3: O(log k) replace farthest
        }
    }
    return heap.entries().map(([, x, y]) => [x, y]);
}

package main

import (
    "container/heap"
    "fmt"
)

type entry struct{ negDist, x, y int }
type MaxHeap []entry
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].negDist > h[j].negDist }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(entry)) }
func (h *MaxHeap) Pop() any {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

func kClosest(points [][]int, k int) [][]int {
    h := &MaxHeap{}
    heap.Init(h)
    for _, p := range points { // L1: iterate n points
        x, y := p[0], p[1]
        d := -(x*x + y*y)
        if h.Len() < k {
            heap.Push(h, entry{d, x, y}) // L2: O(log k) push
        } else if d > (*h)[0].negDist {
            heap.Pop(h)
            heap.Push(h, entry{d, x, y}) // L3: O(log k) replace farthest
        }
    }
    result := make([][]int, h.Len())
    for i, e := range *h { result[i] = []int{e.x, e.y} }
    return result
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    r := kClosest([][]int{{1, 3}, {-2, 2}}, 1)
    assert(len(r) == 1 && r[0][0] == -2 && r[0][1] == 2)
    r2 := kClosest([][]int{{3, 3}, {5, -1}, {-2, 4}}, 2); assert(len(r2) == 2)
    r3 := kClosest([][]int{{0, 0}}, 1); assert(len(r3) == 1)
    r4 := kClosest([][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, 2); assert(len(r4) == 2)
    r5 := kClosest([][]int{{1, 2}, {3, 4}, {0, 0}}, 3); assert(len(r5) == 3)
    fmt.Println("all tests pass")
}

func main() { runTests() }

private struct PointEntry { let point: [Int]; let distance: Int }
final class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        var heap = BinaryHeap<PointEntry> { $0.distance != $1.distance ? $0.distance > $1.distance : ($0.point[0] != $1.point[0] ? $0.point[0] > $1.point[0] : $0.point[1] > $1.point[1]) }
        for point in points { heap.insert(PointEntry(point: point, distance: point[0] * point[0] + point[1] * point[1])); if heap.count > k { _ = heap.removeRoot() } }
        var result: [[Int]] = []; while let entry = heap.removeRoot() { result.append(entry.point) }; return result.sorted(by: isCloser)
    }
    private func isCloser(_ a: [Int], _ b: [Int]) -> Bool { let da = a[0] * a[0] + a[1] * a[1]; let db = b[0] * b[0] + b[1] * b[1]; return da == db ? (a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]) : da < db }
}

Where the time goes, line by line

Variables: n = number of points, k = number of closest points to return.

Line	Per-call cost	Times executed	Contribution
L1 (loop)	$O(1)$	n	$O(n)$
L2 (heappush)	$O(log k)$	up to k	$O(k log k)$
L3 (heapreplace)	$O(log k)$	up to n - k	$O(n log k)$ ← dominates

For the first k points, each push costs $O(log k)$ . For the remaining n - k points, each potential replace also costs $O(log k)$ . Total: $O(n log k)$ .

Complexity

Time: $O(n log k)$ , driven by L2/L3.
Space: $O(k)$ .

Strictly better than Approach 1 when k ≪ n.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Quickselect (optimal average)

Partition the array in place so the first k elements are the k closest (unordered). Average $O(n)$ .

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

    def partition(lo, hi):                           # L1: O(hi - lo) per call
        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

    def quickselect(lo, hi, k):
        if lo >= hi:                                 # L2: base case
            return
        p = partition(lo, hi)                        # L3: O(subarray size)
        if p == k:
            return
        if p < k:
            quickselect(p + 1, hi, k)               # L4: recurse right
        else:
            quickselect(lo, p - 1, k)               # L5: recurse left

    quickselect(0, len(points) - 1, k)
    return points[:k]

function kClosest(points: number[][], k: number): number[][] {
    const arr = points.map(p => [...p]); // avoid mutating input

    const dist = (p: number[]) => p[0] * p[0] + p[1] * p[1];

    function partition(lo: number, hi: number): number {  // L1: O(hi - lo) per call
        const pivot = dist(arr[hi]);
        let store = lo;
        for (let i = lo; i < hi; i++) {
            if (dist(arr[i]) <= pivot) {
                [arr[store], arr[i]] = [arr[i], arr[store]];
                store++;
            }
        }
        [arr[store], arr[hi]] = [arr[hi], arr[store]];
        return store;
    }

    function quickselect(lo: number, hi: number, k: number): void {
        if (lo >= hi) return;                       // L2: base case
        const p = partition(lo, hi);               // L3: O(subarray size)
        if (p === k) return;
        if (p < k) quickselect(p + 1, hi, k);     // L4: recurse right
        else quickselect(lo, p - 1, k);            // L5: recurse left
    }

    quickselect(0, arr.length - 1, k);
    return arr.slice(0, k);
}

package main

import "fmt"

func kClosest(points [][]int, k int) [][]int {
    arr := make([][]int, len(points))
    for i, p := range points { arr[i] = []int{p[0], p[1]} }
    dist := func(p []int) int { return p[0]*p[0] + p[1]*p[1] }

    var partition func(lo, hi int) int
    partition = func(lo, hi int) int { // L1: O(hi - lo) per call
        pivot := dist(arr[hi]); store := lo
        for i := lo; i < hi; i++ {
            if dist(arr[i]) <= pivot { arr[store], arr[i] = arr[i], arr[store]; store++ }
        }
        arr[store], arr[hi] = arr[hi], arr[store]
        return store
    }

    var quickselect func(lo, hi, k int)
    quickselect = func(lo, hi, k int) {
        if lo >= hi { return } // L2: base case
        p := partition(lo, hi) // L3: O(subarray size)
        if p == k { return }
        if p < k { quickselect(p+1, hi, k) } else { quickselect(lo, p-1, k) } // L4/L5
    }

    quickselect(0, len(arr)-1, k)
    return arr[:k]
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    r := kClosest([][]int{{1, 3}, {-2, 2}}, 1); assert(len(r) == 1)
    r2 := kClosest([][]int{{3, 3}, {5, -1}, {-2, 4}}, 2); assert(len(r2) == 2)
    r3 := kClosest([][]int{{0, 0}}, 1); assert(len(r3) == 1)
    r4 := kClosest([][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, 2); assert(len(r4) == 2)
    r5 := kClosest([][]int{{1, 2}, {3, 4}, {0, 0}}, 3); assert(len(r5) == 3)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class Solution {
    func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
        var values = points; var low = 0; var high = values.count - 1
        while low <= high { let pivot = partition(&values, low, high); if pivot == k - 1 { break }; if pivot < k - 1 { low = pivot + 1 } else { high = pivot - 1 } }
        return Array(values.prefix(k)).sorted(by: isCloser)
    }
    private func partition(_ values: inout [[Int]], _ low: Int, _ high: Int) -> Int { let pivot = values[high]; var store = low; for index in low..<high where isCloser(values[index], pivot) { values.swapAt(store, index); store += 1 }; values.swapAt(store, high); return store }
    private func isCloser(_ a: [Int], _ b: [Int]) -> Bool { let da = a[0] * a[0] + a[1] * a[1]; let db = b[0] * b[0] + b[1] * b[1]; return da == db ? (a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]) : da < db }
}

Where the time goes, line by line

Variables: n = number of points, k = number of closest points to return.

Line	Per-call cost	Times executed	Contribution
L1-L3 (partition)	$O(subarray size)$	log n avg rounds	$O(n)$ avg
L4 or L5 (recurse)	$O(1)$ per frame	log n avg	$O(n)$ avg ← dominates

On average each partition halves the search space: n + n/2 + n/4 + … = 2n = $O(n)$ . Worst case $O(n²)$ when pivot is always the extreme (use random pivot to mitigate).

Complexity

Time: $O(n)$ average, $O(n²)$ worst case (L1-L3 partition cost).
Space: $O(log n)$ recursion depth.

Pick quickselect when you’re allowed to mutate the input and want the tightest average complexity.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

# Quick smoke tests, paste into a REPL or save as test_973.py and run.
# Uses the size-K max-heap approach (Approach 2).
import heapq

def k_closest(points, k):
    heap = []
    for x, y in points:
        d = -(x * x + y * y)
        if len(heap) < k:
            heapq.heappush(heap, (d, x, y))
        elif d > heap[0][0]:
            heapq.heapreplace(heap, (d, x, y))
    return [[x, y] for _, x, y in heap]

def _run_tests():
    # Example 1: k=1, closest is [-2,2] (dist=8 vs 10)
    result = k_closest([[1,3],[-2,2]], 1)
    assert result == [[-2,2]], f"got {result}"

    # Example 2: k=2, answer is [[3,3],[-2,4]] (order doesn't matter)
    result = k_closest([[3,3],[5,-1],[-2,4]], 2)
    assert sorted(result) == sorted([[3,3],[-2,4]]), f"got {result}"

    # Single point, k=1
    assert k_closest([[0,0]], 1) == [[0,0]]

    # All equidistant: any k points valid
    result = k_closest([[1,0],[-1,0],[0,1],[0,-1]], 2)
    assert len(result) == 2

    # k equals n: return all
    pts = [[1,2],[3,4],[0,0]]
    result = k_closest(pts, 3)
    assert len(result) == 3

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses the size-K max-heap approach (Approach 2).
// See 973-k-closest-points-to-origin-approach2.ts for the full implementation.
const sortFn = (a: number[], b: number[]) => a[0] - b[0] || a[1] - b[1];

let result = kClosest([[1,3],[-2,2]], 1);
console.assert(JSON.stringify(result) === JSON.stringify([[-2,2]]), `got ${JSON.stringify(result)}`);

result = kClosest([[3,3],[5,-1],[-2,4]], 2);
console.assert(
    JSON.stringify(result.slice().sort(sortFn)) === JSON.stringify([[3,3],[-2,4]].sort(sortFn)),
    `got ${JSON.stringify(result)}`
);

console.assert(JSON.stringify(kClosest([[0,0]], 1)) === JSON.stringify([[0,0]]));

result = kClosest([[1,0],[-1,0],[0,1],[0,-1]], 2);
console.assert(result.length === 2);

result = kClosest([[1,2],[3,4],[0,0]], 3);
console.assert(result.length === 3);

console.log("all tests pass");

Summary

Approach	Time	Space
Sort	$O(n log n)$	$O(n)$
Size-K max-heap	$O(n log k)$	$O(k)$
Quickselect	$O(n)$ avg / $O(n²)$ worst	$O(log n)$

The heap version is the canonical interview answer. Quickselect is the “optimal-average” answer; know it for when the interviewer pushes on tighter bounds.

Heaps / Priority Queues, size-K top/bottom heap template
Arrays, in-place partitioning for quickselect

Top K, the selection pattern for keeping only the best K items instead of sorting everything.
Heap and Priority Queue, the priority frontier for repeatedly taking the smallest, largest, or most urgent item.

973. K Closest Points to Origin (Medium)

Problem

Try it yourself

Approach 1: Brute force, sort by squared distance

Approach 2: Size-K max-heap

Approach 3: Quickselect (optimal average)

Test cases

Summary

Related data structures

Related concepts