Given a list of points points[i] = [x, y] on a plane and an integer k, return the k points closest to the origin (0, 0) using Euclidean distance. The answer is unique apart from its order, and you may return the points in any order.
Example 1
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Squared distances are 10 and 8, so
[-2,2] is closer.Example 2
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Squared distances are 18, 26 and 20.
Constraints
- 1 <= k <= points.length <= 10^4
- -10^4 <= x, y <= 10^4
Hints
Frequently asked at: Meta, Amazon, Apple, LinkedIn
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting all points by distance costs O(n log n). We only need the k closest, so keep a max-heap of size k: its top is the farthest of the current best k. Each new point goes in, and if the heap grows past k we pop the farthest. What remains are the k closest points. Comparing squared distances avoids slow and imprecise square roots.
Algorithm
- For each point compute
d = x*x + y*y. - Push
(d, point)into a max-heap (in Python push-dinto a min-heap). - If the heap size exceeds
k, pop the farthest point. - Return the points left in the heap.
Time:
O(n log k)Space: O(k)Interview tip: A follow-up is points arriving as a stream: the size-k heap handles that naturally, while sorting or quickselect needs all points at once. Quickselect gives average O(n) when everything is available.
class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: heap = [] # (-distance, x, y): the farthest kept point is on top for x, y in points: heapq.heappush(heap, (-(x * x + y * y), x, y)) if len(heap) > k: heapq.heappop(heap) # drop the farthest return [[x, y] for _, x, y in heap]Ctrl + Enter runs the examples