K Closest Points to Origin

Medium

The problem

Each point is [x, y] on a flat plane. Return the k points that are closest to the origin (0, 0), using normal straight-line distance. The points in the answer can be in any order.

Example 1
Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
(-2, 2) is closer to the origin than (1, 3).
Example 2
Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]
Squared distances are 18, 26 and 20, so the two smallest belong to (3, 3) and (-2, 4).

Limits

1 ≤ k ≤ points.length ≤ 100,000
-10,000 ≤ x, y ≤ 10,000
The answer is guaranteed to be unique apart from its order

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You do not need exact distances — comparing squared distances is enough. Keep only the k best.

The idea

Max-heap of size k keyed by squared distance; evict the farthest when size > k.

Target: O(n log k) time

Go function shape

func kClosest(points [][]int, k int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// KClosest keeps a MAX-heap of the k closest points so far (keyed by squared distance, no square root needed).
// The root is the farthest of the k, the one to evict when a closer point arrives.
type pointHeap [][3]int // {squared distance, x, y}

func (h pointHeap) Len() int           { return len(h) }
func (h pointHeap) Less(i, j int) bool { return h[i][0] > h[j][0] }
func (h pointHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *pointHeap) Push(x any)        { *h = append(*h, x.([3]int)) }
func (h *pointHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func KClosest(points [][]int, k int) [][]int {
	h := &pointHeap{}
	for _, p := range points {
		heap.Push(h, [3]int{p[0]*p[0] + p[1]*p[1], p[0], p[1]})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	out := make([][]int, 0, k)
	for _, e := range *h {
		out = append(out, []int{e[1], e[2]})
	}
	return out
}

Read the lesson: Heap / Top-K