loading

K Closest Points to Origin — Step-by-Step Visualization

mediumLeetCode #973ArrayMathDivide and ConquerSortingHeap (Priority Queue)

Given an array of `points` where `points[i] = [xi, yi]` represents a point on the X-Y plane and an integer `k`, return the `k` closest points to the origin `(0, 0)`. The distance from the origin is the Euclidean distance `sqrt(xi² + yi²)`. You may return the answer in any order.

Algorithm Pattern

Sort by Euclidean Distance

Key Idea

Compare squared distances to avoid computing sqrt. Sort all points by x² + y² and take the first k.

Step-by-Step Approach

  1. Compute dist² = x² + y² for each point.
  2. Sort points by dist².
  3. Return the first k points.

Common Gotchas

  • Use x² + y² instead of sqrt(x² + y²) — same ordering, faster.
  • O(n log n) sort; O(n log k) heap solution exists for large n.

Related Problems

← All problems