Find K nearest Points to Point P in 2-dimensional plane

Solution 1 make heap of size K and collect points by minimal distance O(NLogK) complexity.

Solution 2: Take and array of size N and Sort by distance. Should be used QuickSort (Hoare modification). As answer take first K points. This is too NlogN complexity but it is possible optimize to approximate O(N). If skip sorting of unnecessary sub arrays. When you split array by 2 sub arrays you should take only array where Kth index located. complexity will be : N +N/2 +N/4 + ... = O(N).

Solution 3: search Kth element in result array and takes all point lesser then founded. Exists O(N) alghoritm, similar to search of median.

Notes: better use sqr of distance to avoid of sqrt operations, it will be greater faster if point has integer coordinates.

As interview answer better use Solution 2 or 3.

For just a single query...

Maintain a heap of size k.

For each point, calculate the distance to the point P. Insert that distance into the heap and delete the maximum from the heap if the size of the heap is greater than k.

Running time: O(n log k)

// point_type pt, length_sq(p) { return pt[0] * pt[0] + pt[1] * pt[1]}
// std::vector<point_type> points to search.
// The algorithm should recursion depth to 
//       O(k * log(points.size())), and
// running time to O(points.size()).

std::nth_element(
               points.begin(),
               points.begin() + k,
               points.end(),
               [&pt](point_type const & a)
               {
                    return length_squared(a - pt);
               });

// points[0], ... , points[k - 1] are the closest points to pt

class Solution {
   public int[][] kClosest(int[][] points, int K) {
        double [] combinationArr = new double[points.length];
        Hashtable<Double,int[]> pt = new Hashtable();
        for (int i = 0; i <points.length; i++) {
            int [] in = points[i];
            for (int j = 0; j < in.length - 1; j++) {
                Integer x = in[j];
                Integer y = in[j + 1];

                double powerX=Math.pow(x, 2);
                double powerY = Math.pow(y, 2);
                double combination= (Double)(Math.sqrt(powerX + powerY));
                pt.put(combination, points[i]);
                combinationArr[i] = combination;
            }

        }

        Arrays.sort(combinationArr);
        int [][] kpoints = new int[K][K];
        for (int n = 0; n < K; n++) {
            kpoints[n] = pt.get(combinationArr[n]);
        }
       return kpoints;
}
}    

C# Solution using LINQ

public int[][] KClosest(int[][] points, int[][] p, int K) {

    var orderedPoints = points.OrderBy(point => Math.Pow(point[0]-p[0], 2) + Math.Pow(point[1]-p[1], 2));
    return orderedPoints.Take(K).ToArray();
}

public static void NearestPoints() {
    int[][] Points = { new int[] { -16, 5 },
                       new int[] { -1, 2 },
                       new int[] { 4, 3 },
                       new int[] { 10, -2 },
                       new int[] { 0, 3 },
                       new int[] {- 5, -9 } };
    // Linq Order by default use quick sort which will be best suited in this.
    var orderPoint = from i in Enumerable.Range(0, Points.Length)
                     orderby Math.Sqrt( Points[i][0] * Points[i][0] 
                                         + Points[i][1] * Points[i][1] )
                     select new int[][] { Points[i] };
    var result = orderPoint.Take(3);
}