← Back to Index

📚 K Closest Points to Origin – Java Cheat Sheet

📌 What Is It?

The K Closest Points to Origin problem involves finding the K points closest to the origin (0, 0) from a given list of points in a 2D plane. The distance is calculated using the Euclidean distance formula.

This problem can be efficiently solved using a max-heap to track the farthest points among the closest K points.

🧱 Pattern Template

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(
                b[0] * b[0] + b[1] * b[1],
                a[0] * a[0] + a[1] * a[1]
            )
        );

        // Step 1: Add points to the heap
        for (int[] point : points) {
            maxHeap.offer(point);
            if (maxHeap.size() > k) {
                maxHeap.poll(); // Remove the farthest point
            }
        }

        // Step 2: Extract the K closest points
        int[][] result = new int[k][2];
        while (k > 0) {
            result[--k] = maxHeap.poll();
        }

        return result;
    }
}

📊 Time Complexity

• Heap Operations: O(N log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log K).

✅ Use Cases

• Finding the closest points to a specific location
• Applications in clustering and spatial data analysis
• Efficiently processing large datasets with distance-based constraints

📘 Common LeetCode Problems

• 973. K Closest Points to Origin [Medium] Heap

🧪 Example: K Closest Points to Origin

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

Explanation:
- The distance of (1, 3) from the origin is sqrt(10).
- The distance of (-2, 2) from the origin is sqrt(8).
- The closest point is (-2, 2).

▶️ View Animation

💡 Pro Tips

• Use a max-heap to efficiently track the farthest points among the closest K points.
• Edge cases: empty input, K greater than the number of points.
• Ensure the heap size is limited to K for optimal performance.