Analytics Vidhya
Published in

Analytics Vidhya

K Closest Points to Origin — Day 8(Python)

Photo by park dasol on Unsplash
Distance formula. Source: Khan Academy
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]].
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.)
  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000
class kClosestFinder:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
x2 = y2 = 0
points = sorted(points, key = lambda x:math.sqrt(pow(x[0] - x2, 2) + pow(x[1] - y2, 2)))
return points[:K]
  1. Run the loop for all the points in the list.
  2. Find the distance of the current point from the origin.
  3. Push it to the heap, if the size of the heap is equal to K, then pop from the heap before pushing.
  4. Return the final heap.
import heapq
class kClosestFinder:
def calculate_distance(self, x1, x2, y1, y2):
return(math.sqrt(((x2-x1)**2) + (y1-y2)**2))

def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
heap_list = []
for (x, y) in points:
dist = -self.calculate_distance(x, 0, y, 0)
if len(heap_list) == K:
heapq.heappushpop(heap_list, (dist, x, y))
else:
heapq.heappush(heap_list, (dist, x, y))

return [(x,y) for (dist,x, y) in heap_list]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store