##### Welcome to Subscribe On Youtube
• import java.util.Arrays;
import java.util.PriorityQueue;

/**

973. K Closest Points to Origin

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

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

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

@tag-trie

*/

// @todo: divide and conquer solution
public class K_Closest_Points_to_Origin {

public static void main(String[] args) {
K_Closest_Points_to_Origin out = new K_Closest_Points_to_Origin();
Solution s = out.new Solution();

System.out.println(Arrays.toString(s.kClosest(new int[][]{ {3,3},{5,1},{-2,4} }, 2)));
}

class Solution {
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
// larger at top
(p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]
);

for (int[] p : points) {
pq.offer(p);
if (pq.size() > K) {
pq.poll();
}
}

int[][] res = new int[K][2];

while (K > 0) {
res[--K] = pq.poll();
}

return res;
}

}
}

############

class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) -> {
int d1 = a[0] * a[0] + a[1] * a[1];
int d2 = b[0] * b[0] + b[1] * b[1];
return d1 - d2;
});
return Arrays.copyOfRange(points, 0, k);
}
}

• // OJ: https://leetcode.com/problems/k-closest-points-to-origin/
// Time: O(NlogN)
// Space: O(1)
class Solution {
private:
int dist(vector<int> &p) {
return p[0] * p[0]  + p[1] * p[1];
}
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), [&](auto &a, auto &b) { return dist(a) < dist(b); });
return vector<vector<int>>(points.begin(), points.begin() + K);
}
};

• class Solution(object):
def kClosest(self, points, K):
"""
:type points: List[List[int]]
:type K: int
:rtype: List[List[int]]
"""
dis = []
for p in points:
d = math.sqrt(p[0] ** 2 + p[1] ** 2)
dis.append((d, p))
heapq.heapify(dis)
return [d[1] for d in heapq.nsmallest(K, dis)]

• func kClosest(points [][]int, k int) [][]int {
sort.Slice(points, func(i, j int) bool {
a, b := points[i], points[j]
return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1]
})
return points[:k]
}

• function kClosest(points: number[][], k: number): number[][] {
return points
.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2))
.slice(0, k);
}


• impl Solution {
pub fn k_closest(mut points: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
points.sort_unstable_by(|a, b| {
(a[0].pow(2) + a[1].pow(2)).cmp(&(b[0].pow(2) + b[1].pow(2)))
});
points[0..k as usize].to_vec()
}
}


• class Solution {
public int[][] kClosest(int[][] points, int K) {
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] point1, int[] point2) {
return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
}
});
int[][] closestPoints = new int[K][2];
for (int i = 0; i < K; i++) {
for (int j = 0; j < 2; j++)
closestPoints[i][j] = points[i][j];
}
return closestPoints;
}
}

############

class Solution {
public int[][] kClosest(int[][] points, int k) {
Arrays.sort(points, (a, b) -> {
int d1 = a[0] * a[0] + a[1] * a[1];
int d2 = b[0] * b[0] + b[1] * b[1];
return d1 - d2;
});
return Arrays.copyOfRange(points, 0, k);
}
}

• // OJ: https://leetcode.com/problems/k-closest-points-to-origin/
// Time: O(NlogN)
// Space: O(1)
class Solution {
private:
int dist(vector<int> &p) {
return p[0] * p[0]  + p[1] * p[1];
}
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
sort(points.begin(), points.end(), [&](auto &a, auto &b) { return dist(a) < dist(b); });
return vector<vector<int>>(points.begin(), points.begin() + K);
}
};

• class Solution(object):
def kClosest(self, points, K):
"""
:type points: List[List[int]]
:type K: int
:rtype: List[List[int]]
"""
dis = []
for p in points:
d = math.sqrt(p[0] ** 2 + p[1] ** 2)
dis.append((d, p))
heapq.heapify(dis)
return [d[1] for d in heapq.nsmallest(K, dis)]

• func kClosest(points [][]int, k int) [][]int {
sort.Slice(points, func(i, j int) bool {
a, b := points[i], points[j]
return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1]
})
return points[:k]
}

• function kClosest(points: number[][], k: number): number[][] {
return points
.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2))
.slice(0, k);
}


• impl Solution {
pub fn k_closest(mut points: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
points.sort_unstable_by(|a, b| {
(a[0].pow(2) + a[1].pow(2)).cmp(&(b[0].pow(2) + b[1].pow(2)))
});
points[0..k as usize].to_vec()
}
}