K Closest Points to Origin

Medium Problem 82 of 151 Java and Python

Problem

Given an array of points where points[i] = [xᵢ, yᵢ] and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance. The answer can be in any order and is unique.

Example 1

Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Why: Distances² are 10 and 8.

Example 2

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

Constraints

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xᵢ, yᵢ ≤ 10⁴

Explanation

Compare squared distances x² + y²: the square root does not change the order.

Like Kth Largest: keep the k closest points in a max-heap by distance. A new point closer than the farthest one in the heap replaces it.

Approach 1 · Naive

Sort by distance

Time O(n log n)
Space O(n)

Sort all points by squared distance and take the first k.

Sort with key x² + y².
Return the first k points.

Java

import java.util.*;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] sorted = points.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0] * a[0] + a[1] * a[1], b[0] * b[0] + b[1] * b[1]));
        return Arrays.copyOf(sorted, k);
    }
}

Python

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        return sorted(points, key=lambda p: p[0] * p[0] + p[1] * p[1])[:k]

Approach 2 · Optimal

Max-heap of size k

Time O(n log k)
Space O(k)

Keep the k closest points in a max-heap ordered by distance; evict the farthest whenever the heap grows past k.

For each point, push it with its squared distance.
If the heap holds more than k, pop the farthest.
Return the points left in the heap.

Java

import java.util.*;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(b[0] * b[0] + b[1] * b[1], a[0] * a[0] + a[1] * a[1]));
        for (int[] point : points) {
            heap.offer(point);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.toArray(new int[0][]);
    }
}

Python

import heapq

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []  # (-distance, x, y): the farthest point is on top
        for x, y in points:
            heapq.heappush(heap, (-(x * x + y * y), x, y))
            if len(heap) > k:
                heapq.heappop(heap)
        return [[x, y] for _, x, y in heap]

Complexity compared

Approach	Time	Space
Naive Sort by distance	O(n log n)	O(n)
Optimal Max-heap of size k	O(n log k)	O(k)

Key takeaways

Skip square roots when only the order of distances matters.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem