The Runtime Theory
mediumLeetCode#heap#selection

K Closest Points to Origin

Return k points with the smallest squared Euclidean distance to the origin.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inpoints=[[1,3],[-2,2]], k=1

out[[-2,2]]

inpoints=[[3,3],[5,-1],[-2,4]], k=2

out[[3,3],[-2,4]]

inpoints=[[0,1]], k=1

out[[0,1]]

Return k points with the smallest squared Euclidean distance to the origin.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain the time and space complexity in terms of the input sizes and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs covered by the contract.

Reasoning prompt

Squared distance avoids square roots. Compare sorting all points with maintaining a bounded heap; output order may be arbitrary.

Use the linked judge for the canonical problem. The examples above are compact TRT checks; write additional cases before submitting, especially for the boundary that tends to break your chosen invariant.

More practice in this topic

hard · heapFind Median from Data Streammedium · heapFind K Pairs with Smallest Sumsmedium · heapKth Largest Element in an Array

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save