973. K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] 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., √(x1 - x2)2 + (y1 - y2)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.

Solution:

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

        for (int[] point : points){
            pq.offer(point);
        }// [1, 3] 1 * 1 + 9
        // [2,2]  2* 2 + * 4 = 8
        //     

        for (int i = 0; i < k; i++){// 1 -1 =0 i < 0
            result[i] = pq.poll();
        }
        // [-2, 2]

        return result;


    }
}

// TC: O(nlogn)
// SC: O(n)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>((d1, d2) -> Integer.compare(distance(d1), distance(d2)));

        for (int[] p : points){
            minHeap.offer(p);
        }

        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++){
            result[i] = minHeap.poll();
        }

        return result;
    }

    private int distance(int[] points){
        return (points[0] * points[0] + points[1] * points[1]);
    }
}

// TC: O(nlogn)
// SC: O(n)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>(k, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                int d1 = distance(o1);
                int d2 = distance(o2);
                if (d1 == d2){
                    return 0;
                }else if (d1 < d2){
                    return -1;
                }else{
                    return 1;
                }
            }
        });

        // add all points to the heap
        for (int[] point : points){
            minHeap.offer(point);

        }

        // Retrieve the closest k points
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++){
            result[i] = minHeap.poll();
        }
        return result;

    }

    private int distance(int[] point){
        return point[0]*point[0] + point[1]*point[1];
    }
}

// TC: O(nlogn)
// SC: O(n)