## 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;
}
``````
Copy The Code &

Input

cmd
points = [[1,3],[-2,2]], k = 1

Output

cmd
[[-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) {
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]);
}
}
``````
Copy The Code &

Input

cmd
points = [[1,3],[-2,2]], k = 1

Output

cmd
[[-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]
}
``````
Copy The Code &

Input

cmd
points = [[3,3],[5,-1],[-2,4]], k = 2

Output

cmd
[[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]
``````
Copy The Code &

Input

cmd
points = [[3,3],[5,-1],[-2,4]], k = 2

Output

cmd
[[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;
}
}
}
``````
Copy The Code &

Input

cmd
points = [[1,3],[-2,2]], k = 1

Output

cmd
[[-2,2]]