K Closest Points to Origin

Mediumheapsortinggeometry
Category: Heap / Priority Queue
Companies that ask this question:
AmazonFacebookGoogleMicrosoftAsana
LeetCode →NeetCode →

Approach

K Closest Points to Origin

Problem Statement

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: sqrt((x1 - x2)² + (y1 - y2)²).

You may return the answer in any order.

Examples

Example 1

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

Explanation:
Distance from [1,3] to origin = sqrt(1² + 3²) = sqrt(10) ≈ 3.16
Distance from [-2,2] to origin = sqrt(4 + 4) = sqrt(8) ≈ 2.83
Closest point is [-2,2]

Example 2

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

Distances: [18, 26, 20]
Two closest are [3,3] and [-2,4]

Intuition

We need the k smallest distances, which suggests:

  1. Min-heap: Track all points, extract k smallest
  2. Max-heap of size k: Track only k closest (better!)

Optimization: We don't need exact distances, just relative ordering. Use squared distance to avoid expensive sqrt().

Distance² = x² + y²

Pattern Recognition

This is a Max-Heap Top-K problem:

  • Maintain k smallest elements
  • Use max-heap to efficiently remove largest
  • Similar to "Kth Largest" but inverted

Approach

Max-Heap of Size k (Optimal)

  1. Build max-heap of size k based on distance²
  2. For remaining points:
    • If point closer than farthest in heap:
      • Remove farthest (pop)
      • Add new point (push)
  3. Return all k points in heap

Time: O(n log k) - better than sorting all points O(n log n)

Quick Select (Alternative)

Can achieve O(n) average, but more complex implementation.

Sorting (Simple but Slower)

Sort all points by distance, take first k: O(n log n)

Edge Cases

  • k = 1 (closest point only)
  • k = n (return all points)
  • Points at same distance
  • Points at origin ([0,0])
  • Negative coordinates

Complexity Analysis

Max-Heap Approach

  • Time: O(n log k)

    • Build heap with first k: O(k log k)
    • Process remaining n-k: O((n-k) log k)
    • Total: O(n log k)

  • Space: O(k)

    • Store k points in heap

Sorting Approach

  • Time: O(n log n)
  • Space: O(1) or O(n) depending on sort

Solution

java
1import java.util.PriorityQueue;
2
3class Solution {
4    public int[][] kClosest(int[][] points, int k) {
5        // Max-heap storing points by distance (farthest at top)
6        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
7            (a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1])
8        );
9
10        for (int[] point : points) {
11            if (maxHeap.size() < k) {
12                // Heap not full, add point
13                maxHeap.offer(point);
14            } else {
15                int[] farthest = maxHeap.peek();
16                int dist = point[0] * point[0] + point[1] * point[1];
17                int farthestDist = farthest[0] * farthest[0] + farthest[1] * farthest[1];
18
19                if (dist < farthestDist) {
20                    // Point is closer than farthest in heap
21                    maxHeap.poll();
22                    maxHeap.offer(point);
23                }
24            }
25        }
26
27        // Convert heap to array
28        int[][] result = new int[k][2];
29        for (int i = 0; i < k; i++) {
30            result[i] = maxHeap.poll();
31        }
32
33        return result;
34    }
35}
36
Loading visualizer...