Medium

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., sqrt((x1 - x2)^2 + (y1 - y2)^2))`. You may return the answer in any order.

Examples

Input:points = [[1,3],[-2,2]], k = 1

Output:[[-2,2]]

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.

Input:points = [[3,3],[5,-1],[-2,4]], k = 2

Output:[[3,3],[-2,4]]

Constraints

1 <= k <= points.length <= 10^4
-10^4 <= xi, yi <= 10^4

Approach

To find the `k` smallest distances, we can maintain a Max Heap of size `k`. Iterate through the points, calculate their squared distance from the origin (no need to compute the square root). Push the `[distance, x, y]` into the Max Heap. If the heap size exceeds `k`, pop the largest element (which is at the root). This ensures the heap only contains the `k` closest points. Finally, extract the points from the heap.

Complexity Analysis

Time Complexity

O(N log K)

Space Complexity

O(K)

This is O(K) space because we only keep K elements in the heap.

Solution.java

1class Solution {2    public int[][] kClosest(int[][] points, int k) {3        // Max Heap: sort by distance descending4        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> 5            Integer.compare(6                (b[0] * b[0] + b[1] * b[1]), 7                (a[0] * a[0] + a[1] * a[1])8            )9        );10        11        for (int[] point : points) {12            maxHeap.offer(point);13            if (maxHeap.size() > k) {14                maxHeap.poll();15            }16        }17        18        int[][] result = new int[k][2];19        int i = 0;20        while (!maxHeap.isEmpty()) {21            result[i++] = maxHeap.poll();22        }23        24        return result;25    }26}