Our May 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

**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.

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

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

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

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