King Of Interviews

K Closest Points to Origin: Given an array of points where points[i] = [x_i, y_i] 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., √(x_1 - x_2)^2 + (y_1 - y_2)^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 <= 10^4
-10^4 < x_i, y_i < 10^4

Try this Problem on your own or check similar problems:

Solution:

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));

    for(int i = 0; i < points.length; ++i){
        pq.add(points[i]);
        if(pq.size() > k){
            pq.poll();
        }
    }

    return pq.toArray(new int[k][2]);
}

Time/Space Complexity:

Time Complexity: O(nlogk)
Space Complexity: O(k)

Explanation:

Most of the time when we have the closest/minimum as desired result we want to create a maxheap, otherwise when we have farthest/maximum we want to keep minheap. Heap in this case is the holder of candidates, each time we go over k candidates we must discard some element from the heap. In our case since we are looking for the closest points, it’s best to discard the point which the farthest from the origin, that’s why we keep the maxheap and define the comparison to be (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]) basically comparing distance from the origin by the formula given by problem statement. We iterate over the points and keep the k candidates (each time discarding the farthest point when we go over k candidates). Finally, we convert the priority queue to an array and return it as our result. The time complexity is determined by time spent iterating over all points n and the job done for each iteration (at most log k for discarding/polling the element from the queue of size k), while the space complexity is determined by the size of the queue which is k.

K Closest Points to Origin