# How do I find k nearest neighbours of a given point from a set of points in a plane in O(n)?

Let’s call the given point be P and set of points be S. Iterate over S and find distance between each point in S and P using Euclidean distance formula (d = √[(x2 – x1)2 + (y2 – y1)2]). Store these distances in an array. Let’s call this array distances[]. Most obvious solution, seems to sort this array distances[] and get first k nearest neighbours. This algorithm is 𝑂(𝑛𝑙𝑜𝑔𝑛). Here’s a C++ code:

//How do I find k nearest neighbours of a given point?
//Created by Himanshu on 08/07/21.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#define N 5
using namespace std;

struct Point {
int pos;
double distance;
};

bool comp(const Point &a, const Point &b) {
return (a.distance < b.distance);
}

void solve(int inpPoints[N], int inpPoint, int k) {

vector<vector<int>> nearestNeighbours(k, vector<int> (2, 0));

struct Point points[N];
for (int i=0; i<N; i++) {
points[i].distance = sqrt(((inpPoints[i]-inpPoint)*(inpPoints[i]-inpPoint)) + ((inpPoints[i]-inpPoint)*(inpPoints[i]-inpPoint)));
points[i].pos = i;
}
sort(points, points+N, comp);
printf("%d nearest neighbours to Point(0, 0) are\n", k);

for (int i=0; i<k; i++) {
cout<<inpPoints[points[i].pos]<<" "<<inpPoints[points[i].pos]<<"\n";
nearestNeighbours[i].push_back(inpPoints[points[i].pos]);
nearestNeighbours[i].push_back(inpPoints[points[i].pos]);
}
}

int main() {

int k = 2;
int points[N] = { {8, 4}, {2, 5}, {1, 1}, {2, 8}, {7, 1} };
int point[] = {0, 0};
solve(points, point, k);
return 0;
}


#### But we can do better than that. We can solve this in 𝑂(𝑛).

Make a min heap out of this array distances[]. This step is 𝑂(𝑛). (You can read more about binary heap here.) Now, extract minimum element from this heap using extractMin operation of heap. Operation extractMin takes 𝑂(𝑙𝑜𝑔𝑛) time. Calling it k times, you get the running time as 𝑂(𝑛+𝑘𝑙𝑜𝑔𝑛).

Here’s a C++ program using Heap provided by C++ library:

//How do I find k nearest neighbours of a given point in O(n)?
//Created by Himanshu on 08/07/21.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#define N 5
using namespace std;

struct Point {
int pos;
double distance;
};

bool comp(const struct Point &a, const struct Point &b) {
return (a.distance > b.distance);
}

void solve(int inpPoints[N], int inpPoint, int k) {

//    vector<vector<int>> nearestNeighbours(k, vector<int> (2, 0));
//

vector<struct Point> points;
for (int i=0; i<N; i++) {
Point point;
point.distance = sqrt(((inpPoints[i]-inpPoint)*(inpPoints[i]-inpPoint)) + ((inpPoints[i]-inpPoint)*(inpPoints[i]-inpPoint)));
point.pos = i;
points.push_back(point);
}
make_heap(points.begin(), points.end(), &comp);

printf("K nearest neighbours to Point(0, 0) are\n");
for (int i=0; i<k; i++) {
struct Point point = points.front();
pop_heap(points.begin(), points.end(), &comp);
points.pop_back();
cout<<inpPoints[point.pos]<<" "<<inpPoints[point.pos]<<"\n";

}

}

int main() {

int k = 2;
int points[N] = { {8, 4}, {2, 5}, {1, 1}, {2, 8}, {7, 1} };
int point[] = {0, 0};
solve(points, point, k);
return 0;
}

Thanks.