Published in

Analytics Vidhya

# K Closest Points to Origin — Day 8(Python)

`Input: points = [[1,3],[-2,2]], K = 1Output: [[-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 = 2Output: [[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 heapqclass 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]`

--

--

## More from Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com