Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] 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<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup>). You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Test Cases

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:

Solution

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> Long.compare(getArea(b), getArea(a)));
        for(int[] point: points) {
            if (pq.size() < k) {
                pq.offer(point);
            } else {
                if (getArea(point) < getArea(pq.peek())) {
                    pq.poll();
                    pq.offer(point);
                }
            }
        }

        int[][] res = new int[k][2];
        while(!pq.isEmpty()) {
            res[--k] = pq.poll();
        }

        return res;
    }

    private long getArea(int[] a) {
        return (a[0]*a[0] + a[1]*a[1]);
    }
}
Time Complexity: O(nlogk)
Space Complexity: O(k)