Algorithm
Problem Name: 973. K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
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]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
1 <= k <= points.length <= 104-104 < xi, yi < 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int i;
int d;
} p_t;
int cmp(const void *a, const void *b) {
const p_t *p1 = a;
const p_t *p2 = b;
if (p1->d < p2->d) return -1;
else if (p1->d == p2->d) return 0;
return 1;
}
void swap(void *a, void *b) {
p_t *p1 = a;
p_t *p2 = b;
p_t t = *p1;
*p1 = *p2;
*p2 = t;
}
void hsort(void *p, int n, int l,
int (*f)(const void *, const void *),
void (*s)(void *, void *)) {
int d;
const void *t;
if (n < 2) return;
t = p;
while (n -- > 1) {
p += l;
if (f(t, p) < 0) {
t = p;
}
}
if (t != p) {
s(t, p);
}
}
int** kClosest(int** points, int pointsRowSize, int *pointsColSizes, int K, int* returnSize, int** columnSizes) {
p_t *a;
int i, x, y, d;
int **p, *col, *buff;
a = malloc((K + 1) * sizeof(p_t));
//assert(a);
for (i = 0; i < = K && i < pointsRowSize; i ++) {
x = points[i][0]; y = points[i][1];
d = x * x + y * y;
a[i].i = i;
a[i].d = d;
}
if (i > K) {
// TODO: optimize by using binary search tree for heap sort
hsort(a, K + 1, sizeof(p_t), cmp, swap);
}
while (i < pointsRowSize) {
x = points[i][0]; y = points[i][1];
d = x * x + y * y;
if (d < a[K].d) { // replace the point on the top of the heap
a[K].i = i;
a[K].d = d;
hsort(a, K + 1, sizeof(p_t), cmp, swap);
}
i ++;
}
buff = malloc(K * 2 * sizeof(int));
p = malloc(K * sizeof(int *));
col = malloc(K * sizeof(int));
for (i = 0; i < K; i ++) {
buff[i * 2 ] = points[a[i].i][0];
buff[i * 2 + 1] = points[a[i].i][1];
p[i] = &buff[i * 2];
col[i] = 2;
}
*columnSizes = col;
*returnSize = K;
free(a);
return p;
}
Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[][] kClosest(int[][] points, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> getDistance(o2) - getDistance(o1));
for (int[] point : points) {
pq.add(point);
if (pq.size() > k) {
pq.poll();
}
}
int[][] result = new int[pq.size()][2];
for (int i = 0; i < result.length; i++) {
result[i] = pq.poll();
}
return result;
}
private int getDistance(int[] point) {
return (point[0] * point[0]) + (point[1] * point[1]);
}
}
Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const kClosest = (points, K) => {
let len = points.length,
l = 0,
r = len - 1
while (l <= r) {
let mid = helper(points, l, r)
if (mid === K) break
if (mid < K) {
l = mid + 1
} else {
r = mid - 1
}
}
return points.slice(0, K)
}
function helper(A, l, r) {
let pivot = A[l]
let ll = l
while (l < r) {
while (l < r && compare(A[r], pivot) >= 0) r--
while (l < r && compare(A[l], pivot) <= 0) l++
swap(A, l, r)
}
swap(A, ll, l)
return l
}
function swap(arr, i, j) {
let tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
function compare(p1, p2) {
return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]
}
Input
points = [[3,3],[5,-1],[-2,4]], k = 2
Output
[[3,3],[-2,4]]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def kClosest(self, points, K):
return sorted(points, key = lambda p: p[0] ** 2 + p[1] ** 2)[:K]
Input
points = [[3,3],[5,-1],[-2,4]], k = 2
Output
[[3,3],[-2,4]]
#5 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0973_KClosestPointsToOrigin
{
private readonly Random random = new Random();
public int[][] KClosest(int[][] points, int K)
{
Sort(points, 0, points.Length - 1, K);
var result = new int[K][];
Array.Copy(points, 0, result, 0, K);
return result;
}
private void Sort(int[][] points, int lo, int hi, int k)
{
if (lo >= hi) return;
var randomIndex = random.Next(lo, hi);
Swap(points, lo, randomIndex);
var mid = Partition(points, lo, hi);
var length = mid - lo + 1;
if (length > k)
Sort(points, lo, mid - 1, k);
else
Sort(points, mid + 1, hi, k - length);
}
private int Partition(int[][] points, int lo, int hi)
{
int i = lo, j = hi + 1;
var pivotDistance = GetDistance(points, lo);
while (true)
{
while (GetDistance(points, ++i) < pivotDistance) if (i == hi) break;
while (GetDistance(points, --j) > pivotDistance) if (j == lo) break;
if (i >= j) break;
Swap(points, i, j);
}
Swap(points, lo, j);
return j;
}
private int GetDistance(int[][] points, int i)
{
return points[i][0] * points[i][0] + points[i][1] * points[i][1];
}
private void Swap(int[][] points, int i, int j)
{
int t0 = points[i][0], t1 = points[i][1];
points[i][0] = points[j][0];
points[i][1] = points[j][1];
points[j][0] = t0;
points[j][1] = t1;
}
}
}
Input
points = [[1,3],[-2,2]], k = 1
Output
[[-2,2]]