Given a list of points on a 2D plane. Find k closest points to origin (0, 0).
Input: points = [[1,3],[-2,2],[5,5]], k = 2
Output: [[-2,2],[1,3]]
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)** is less than **sqrt(10)**, (-2, 2) is closer to the origin. We only want the **closest k = 2** points from the origin, so the answer is just **[[-2,2],[1,3]]**.
Before we dive into the solution, the .Distance between two points (x1, y1) and (x2, y2) is.
$$ \sqrt{\left(x1-x2\right)^2+\left(y1-y2\right)^2} $$
For the point (-2,-2). The coordinates of the first point, (x1, y1), are (0, 0) and the coordinates of the second point, (x2, y2), are (-2, -2), so the distance from the origin to this point can be calculated as follows
$$ \sqrt{\left(0-(-2)\right)^2+\left(0-(-2)\right)^2}= \sqrt{8} $$
For the points (-2,-2), (5,5), and (1,3), the distances will be, respectively.
$$ \sqrt{8}, \sqrt{25}, \sqrt{10} $$
As we discussed in Similar Questions: Kth Element, when we encounter a problem involving "closest k", our first reaction should be to use heaps.
The first part element in the payload to the heap is used to sort the data inside the heap. We can add different types of data in the second or even third element and they will not play any part in the sorting.
Elements
First element (sorting): Distance
Second Element (information) : coordinates.
Something like in the image below
We can start with a heap of size k. These will be assumed to be the closest k points to the origin among the first k values from array points. (Don't forget to multiply -1 while adding to the heap in Python to simulate a max heap.)
for i in range(k):
x2 = points[i][0]
y2 = points[i][1]
distance = self.calculateDistance(x2,y2)
coordinates = (x2,y2)
heappush(heap,(-1 *distance,coordinates))
function for calculating distance
def calculateDistance(self,x2,y2):
#origin(coordinates)
x1 = 0
y1 = 0
#calculate
radicand = (x1-x2)**2 + (y1-y2)**2
distance = sqrt(radicand)
return distance