'k closest point to origin
I am trying to solve this problem. https://leetcode.com/problems/k-closest-points-to-origin/ I have used maxheap and following is my code. This works well for points= [[1,3],[-2,2]], k = 1. However for points = [[3,3],[5,-1],[-2,4]], k = 2, this is giving the output as [[3,3],[5,-1]] whereas the expected output is [[3,3],[-2,4]]. I am not being able to figure out why my code is picking the point [5,-1]. Please help find the mistake I am doing.
from heapq import *
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
maxHeap = []
for i in range(k):
heappush(maxHeap, points[i])
for i in range(k, len(points)):
dist = self.distance(points[i])
heapdistance_from_origin = self.distance(maxHeap[0])
if dist < heapdistance_from_origin:
heappop(maxHeap)
heappush(maxHeap, points[i])
return maxHeap
def distance(self, point: List[int]):
return point[0] * point[0] + point[1] * point[1]
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
