// Runtime: 33 ms, faster than 47.34% of Java online submissions for K Closest Points to Origin.
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return b[0]*b[0] + b[1]*b[1] - (a[0]*a[0] + a[1]*a[1]);
                }
            });

        for (int[] point: points) {
            pq.add(point);

            if (pq.size() > K) pq.poll();
        }

        int[][] result = new int[K][];

        for (int i = K-1; i >=0; i--) {
            int[] point = pq.poll();
            result[i] = point;
        }

        return result;
    }
}

// Runtime: 25 ms, faster than 61.65% of Java online submissions for K Closest Points to Origin.
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Arrays.sort(points,
            new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return a[0]*a[0] + a[1]*a[1] - (b[0]*b[0] + b[1]*b[1]);
                }
            });

        int[][] result = new int[K][];

        for (int i = 0; i < K; i++) {
            result[i] = points[i];
        }

        return result;
    }
}