## Description

https://leetcode.com/problems/missing-ranges/

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 = 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]].

**Example 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.)

**Note:**

`1 <= K <= points.length <= 10000`

`-10000 < points[i][0] < 10000`

`-10000 < points[i][1] < 10000`

## Explanation

use a priority queue

## Python Solution

```
from queue import PriorityQueue
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
results = []
distances = []
distances = PriorityQueue()
for point in points:
distance = sqrt(point[0]**2 + point[1]**2)
distances.put((distance, point))
for i in range(0, K):
results.append(distances.get()[1])
return results
```

- Time complexity: ~N
- Space complexity: ~N

## One Thought to “LeetCode 973. K Closest Points to Origin”