Java

import java.util.Arrays;
import java.util.PriorityQueue;

/**

 973. K Closest Points to Origin

 We have a list of points on the plane.
 Find the K closest points to the origin (0, 0).
     (Here, the distance between two points on a plane is the Euclidean distance.)

 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]]
 (The answer [[-2,4],[3,3]] would also be accepted.)


 Note:

 1 <= K <= points.length <= 10000
 -10000 < points[i][0] < 10000
 -10000 < points[i][1] < 10000

 @tag-trie

 */

// @todo: divide and conquer solution
public class K_Closest_Points_to_Origin {

    public static void main(String[] args) {
        K_Closest_Points_to_Origin out = new K_Closest_Points_to_Origin();
        Solution s = out.new Solution();

        System.out.println(Arrays.toString(s.kClosest(new int[][]{ {3,3},{5,1},{-2,4} }, 2)));
    }

    class Solution {
        public int[][] kClosest(int[][] points, int K) {
            PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
                // larger at top
                (p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]
            );

            for (int[] p : points) {
                pq.offer(p);
                if (pq.size() > K) {
                    pq.poll();
                }
            }

            int[][] res = new int[K][2];

            while (K > 0) {
                res[--K] = pq.poll();
            }

            return res;
        }

    }
}

Java

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
            }
        });
        int[][] closestPoints = new int[K][2];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 2; j++)
                closestPoints[i][j] = points[i][j];
        }
        return closestPoints;
    }
}

All Problems

All Solutions