973. K Closest Points to Origin

Quick Identifier

Topic: heap-priority-queue
Pattern: Top-K / Heap
Difficulty: Medium
Companies: Meta, Amazon, Google, Microsoft, Apple
Frequency: High
LeetCode: 973

Quick Sights

Time Complexity: O(n) from the optimal approach.
Space Complexity: O(k) from the optimal approach.
Core Mechanism: Given points on a plane and integer k, return the k points with smallest Euclidean distance to (0,0) (order among the k may be any).

Concept Explanation

Given points on a plane and integer k, return the k points with smallest Euclidean distance to (0,0) (order among the k may be any).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Closest / smallest distance → selection problem
Avoid sorting all n points when only k needed — heap or quickselect
Distance squared avoids sqrt for comparisons

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — compute distances, sort — O(n log n) time.
Better — max-heap of size k over distance — O(n log k) time, O(k) space.
Optimal — same heap approach or average O(n) quickselect on squared distance — heap solution is interview-stable.

Optimal Solution

Go

import (
	"container/heap"
)

type pointDist struct {
	row    int
	col    int
	square int
}

type maxHeapPoints []*pointDist

func (heapSlice maxHeapPoints) Len() int { return len(heapSlice) }
func (heapSlice maxHeapPoints) Less(left, right int) bool {
	return heapSlice[left].square > heapSlice[right].square
}
func (heapSlice maxHeapPoints) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *maxHeapPoints) Push(value any) {
	*heapSlice = append(*heapSlice, value.(*pointDist))
}

func (heapSlice *maxHeapPoints) Pop() any {
	old := *heapSlice
	length := len(old)
	value := old[length-1]
	*heapSlice = old[0 : length-1]
	return value
}

func kClosest(points [][]int, k int) [][]int {
	maxHeap := &maxHeapPoints{}
	heap.Init(maxHeap)
	for _, point := range points {
		row := point[0]
		col := point[1]
		square := row*row + col*col
		heap.Push(maxHeap, &pointDist{row: row, col: col, square: square})
		if maxHeap.Len() > k {
			heap.Pop(maxHeap)
		}
	}
	result := make([][]int, 0, k)
	for maxHeap.Len() > 0 {
		top := heap.Pop(maxHeap).(*pointDist)
		result = append(result, []int{top.row, top.col})
	}
	return result
}

JavaScript

class MaxHeap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  peek() {
    return this.data[0];
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parentIndex]) <= 0) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let candidate = index;
      if (
        leftChild < length &&
        this.compare(this.data[leftChild], this.data[candidate]) > 0
      ) {
        candidate = leftChild;
      }
      if (
        rightChild < length &&
        this.compare(this.data[rightChild], this.data[candidate]) > 0
      ) {
        candidate = rightChild;
      }
      if (candidate === index) {
        break;
      }
      this.swap(index, candidate);
      index = candidate;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function kClosest(points, k) {
  const distSq = (point) => point[0] * point[0] + point[1] * point[1];
  const heap = new MaxHeap((leftPoint, rightPoint) =>
    distSq(leftPoint) - distSq(rightPoint)
  );
  for (const point of points) {
    heap.push(point);
    if (heap.size() > k) {
      heap.pop();
    }
  }
  return heap.data;
}

Walkthrough

points = [[1,3],[-2,2]], k = 1. Squared distances: 10 vs 8 → keep [-2,2].

step	point	max-heap (size ≤ k)
1	[1,3]	{10 → [1,3]}
2	[-2,2]	push 8, pop 10

Invariant: Max-heap stores the k smallest distances seen; root is worst among the chosen k.

Edge Cases

k === n → return all points
Duplicate coordinates — valid multiple entries
Negative coordinates — square removes sign issues

Pitfalls

Using min-heap incorrectly for "k smallest" — max-heap of size k is the classic pattern
Using sqrt in comparator — unnecessary; squared distance preserves order

Variants

K farthest points → min-heap by distance or reverse logic
Manhattan distance — replace metric in key

Mind-Map Tags

#heap #max-heap-size-k #geometry #euclidean #top-k-smallest