Nearest Neighbours Problem

Problem Statement:

Given a point p, and other n points in two-dimensional space, find k points out of n points which are nearest to p.

NOTE: Distance between two points is measured by the standard Euclidean method.

‍

Input/Output Format For The Function:

Input Format:

There are 4 arguments in input, an integer p_x, which is the x coordinate of point p, integer p_y, which is the y coordinate of point p, an integer k and a 2D integer array of points n_points.

Output Format:

Return a 2D integer array result, which contains k points, nearest to point p.

‍

Solution

We have provided three solutions and all the solutions contain necessary comments to understand the approach used:

1) brute force solution.java

Description:

We compute the distance of each and every point present in array n_points from point p. After this, we sort the points present in array n_points according to their distances from point p in ascending order. Now we simply take the first k points from the array and append them to the result.

Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):

O(n*log(n)) where n is the size of array n_points.

As we are computing the distance of each and every point present in array n_points from point p this will take O(n) and sorting them takes O(n*log(n)) time.

Time Complexity:

O(n*log(n)) where n is the size of array n_points.

As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n*log(n)), to read input it will take O(n) and to initialise output array it will take O(k) hence total complexity will be O(n*log(n)) + O(n) + O(k) → O(n*log(n)).

Auxiliary Space Used:

O(n) where n is the size of array n_points.

As we create an auxiliary array to store the distances of all the points present in array n_points from point p. It will take extra space equal to the number of points hence it will be O(n).

Space Complexity:

O(n+k) where n is the size of array n_points and k is the number of points nearest to point p, to be returned as output.

For storing input it would take O(n), as we are storing the points in array n_points and auxiliary space used is O(n) and O(k) to store output, hence total complexity will be O(n) + O(n) + O(k) → O(n+k).

// -------- START --------
    public static List<list> nearest_neighbours(int p_x, int p_y, int k, List<list> n_points) {
        int len = n_points.size();
        /*Point is a class with two attributes for each point 
        present n_points- index and distance from point P.*/
        Point[] pnt = new Point[len]; 
        /*We fill the values in pnt array accordingly*/
        for(int i = 0; i<len; i++) {    int x="n_points.get(i).get(0)," y="n_points.get(i).get(1);"  pnt[i]="new" point(i, math.sqrt((p_x-x)*1l*(p_x-x) + (p_y-y)*1l*(p_y-y)));  } *we sort the point array according to distance, that means  having least distance from p would be at lowest index (index 0) and  point with maximum last index.*  arrays.sort(pnt);  list<list> result = new ArrayList<>();
        /*We simply take the top k points and return them as the answer*/
        for(int i = 0; i < k; i++){
            int index = pnt[i].index;
            result.add(n_points.get(index));
        }
        return result;
    }

    static class Point implements Comparable{
        int index;
        double dist;

        public Point(int i, double dist){
            this.index = i;
            this.dist = dist;
        }

        public int compareTo(Point p){
            return Double.compare(this.dist,p.dist);
        }
    }
// -------- END --------

2) suboptimal_solution.java

Description:

We compute the distance of each and every point present in array n_points from point p. Along with this, we create a max heap and add the point whose distance we computed into the max heap. After each insertion, we check if the size of the max heap is less than or equal to k. If it is greater than k, we poll the maximum value out of it. Thus after insertion of all the points present in array n_points, and polling as per the condition mentioned, we will be left with k points having minimum distance.

Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):

O(n*log(k)) where n is the size of the array n_points and k is the number of points nearest to point p, to be returned as output.

As we compute the distance of each point present in array n_points from point p and also maintain a max heap of size k, the complexity is O(n*log(k)).

Time Complexity:

O(n*log(k)) where n is the size of the array n_points and k is the number of points nearest to point p, to be returned as output.

As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n*log(k)), to read input it will take O(n) and to initialise output array it will take O(k) hence total complexity will be O(n*log(k)) + O(n) + O(k) → O(n*log(k)).

Auxiliary Space Used:

O(k) where k is the number of points nearest to point p, to be returned as output.

As we maintain a max heap of size k to store the k elements having the minimum distance from point P. It will take O(k) of extra space.

Space Complexity:

O(n+k) where n is the size of the array n_points and k is the number of points nearest to point p, to be returned as output.

For storing input it would take O(n), as we are storing the points in array n_points and auxiliary space used is O(k) and O(k) to store output, hence total complexity will be O(n) + O(k) + O(k) → O(n+k).

// -------- START --------
    public static List<list> nearest_neighbours(int p_x, int p_y, int k, List<list> n_points) {
        int len = n_points.size();
        /*This priority queue will act as a maxheap, where the points having the
        most distance will be at the front of the queus*/
        PriorityQueue maxHeap = new PriorityQueue<>();
        for(int i = 0; i<len; i++){    int x="n_points.get(i).get(0)," y="n_points.get(i).get(1);" *we keep on adding all the points and ensure that size of heap never  exceeds k. if it does, we poll from it, is remove point having  the most distance p existing in maxheap.*  maxheap.add(new point(i, math.sqrt((p_x-x)*1l*(p_x-x) + (p_y-y)*1l*(p_y-y))));  if(maxheap.size()>k){
                maxHeap.poll();
            }
        }
        /*All the k points in the maxheap are the answers*/
        List<list> result = new ArrayList<>();
        for(Point p : maxHeap){
            int index = p.index;
            result.add(n_points.get(index));
        }
        return result;
    }

    /*Point is a class with two attributes for each point 
        present n_points- index and distance from point P.*/
    static class Point implements Comparable{
        int index;
        double dist;

        public Point(int i, double dist){
            this.index = i;
            this.dist = dist;
        }

        public int compareTo(Point p){
            return Double.compare(p.dist,this.dist);
        }
    }
    // -------- END --------

3) optimal_solution.java

Description:

We compute the distance of each and every point present in array n_points from point p. Now we need to select k points having the minimum distance. For this, we use the quickselect algorithm which is a subpart of the quicksort algorithm. We randomly shuffle the array to reduce the average case running time of quicksort algorithm. We choose a pivot and split the array by the pivot. Now, if the position of pivot decides which array should we split. Note that here we do not need to sort each and every subarray, we will only sort the subarrays which we require. This part is commented well in the code “optimal_solution.java”. Please refer to it in case of any query.

‍

Time Complexity (assuming that input arguments are already given and excluding time used in declaration of output):

O(n) where n is the size of the array n_points.

We compute the distance of each point present of array n_points in O(n). On average, the number of operations required for sorting (only selective sub arrays and skipping the ones not required) turns out to be n + n/2 + n/4 + … ~ 2*n = O(n).

Time Complexity:

O(n+k) where n is the size of the array n_points and k is the number of points nearest to point p, to be returned as output.

As time complexity assuming that input arguments are already given and excluding time used in declaration of output is O(n), to read input it will take O(n) and to initialise output array  it will take O(k) hence total complexity will be O(n) + O(n) + O(k) → O(n+k).

Auxiliary Space Used:

O(n) where n is the size of the array n_points.

As we create an array to store the distance of each point present in array n_points from point p. It will take extra space of O(n).

Space Complexity:

O(n+k) where n is the size of the array n_points and k is the number of points nearest to point p, to be returned as output.

For storing input it would take O(n), as we are storing the points in array n_points and auxiliary space used is O(n) and O(k) to store output, hence total complexity will be O(n) + O(n) + O(k) → O(n+k).

// -------- START --------
    public static List<list> nearest_neighbours(int p_x, int p_y, int k, List<list> n_points) {
        int len = n_points.size();
        /*Point is a class with two attributes for each point 
        present n_points- index and distance from point P.*/
        Point[] pnt = new Point[len];
        for(int i = 0; i<len; i++){    int x="n_points.get(i).get(0)," y="n_points.get(i).get(1);"  pnt[i]="new" point(i, math.sqrt((p_x-x)*1l*(p_x-x) + (p_y-y)*1l*(p_y-y)));  } *shuffle the array points*  pnt="shuffle(pnt,new" random());  list<list> result = new ArrayList<>();
        topK(pnt,k);
        for(int i = 0; i<k; i++){    result.add(n_points.get(pnt[i].index));  }  return result; * get k points having least distance from point p.*  public static void topk(point[] points, int k){  int left="0," right="points.length" - 1; *we just need the smallest points. we dont care whether they are  sorted or not. similarly once possible elements,  we can skip sorting of unnecessary sub arrays.*  while(left<right){ part="split(points," left, right);  if (part="=k)" {  return;  else if(part<k)  left="part+1;"  else{  right="part-1;" *shuffles array randomly* point[] shuffle(point[] a, random gen){  for (int i="0," n="a.length;" < n; ind="gen.nextInt(n" i) + i;  point d="a[i];"  a[i]="a[ind];"  a[ind]="d;" a; *similar to partition function quicksort. it partitions along pivot  such that elements smaller than and larger it.* split(point[] right) piv="points[left];" j="right"  while (true) (i && points[++i].compareto(piv) 0); (j> left && points[--j].compareTo(piv) > 0);
            if (i >= j) {
                break;
            }
            Point temp = points[i];
            points[i] = points[j];
            points[j] = temp;
        }
        Point temp = points[j];
        points[j] = points[left];
        points[left] = temp;
        return j;
    }
    static class Point implements Comparable{
        int index;
        double dist;

        public Point(int i, double dist){
            this.index = i;
            this.dist = dist;
        }

        public int compareTo(Point part){
            return Double.compare(this.dist,part.dist);
        }
    }
    // -------- END --------