K Closest Points to Origin Problem

Question

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

 

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

 

Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

Answer 1

We keep a min heap of size K.

For each item, we insert an item to our heap.

If inserting an item makes heap size larger than k, then we immediately pop an item after inserting ( heappushpop ).

Runtime:

Inserting an item to a heap of size k take O(logK) time.

And we do this for each item points.

So runtime is O(N * logK) where N is the length of points.

Space: O(K) for our heap.

import heapq class Solution:     def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:                  heap = []                  for (x, y) in points:             dist = -(x*x + y*y)             if len(heap) == K:                 heapq.heappushpop(heap, (dist, x, y))             else:                 heapq.heappush(heap, (dist, x, y))                  return [(x,y) for (dist,x, y) in heap]

eg : points = [[1,3],[-2,2]] 

K = 1

ans = Solution()

ans.kClosest(points, K)

Output-

[[-2,2]]