LeetCode 973: K Closest Points to Origin Solution

Master LeetCode problem 973 (K Closest Points to Origin), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

973. K Closest Points to Origin

Medium

Array Math Divide and Conquer Geometry Sorting Heap (Priority Queue)Quickselect

Problem Explanation

Explanation

To solve this problem, we can use a min heap (priority queue) to store the points based on their distance from the origin. We will calculate the Euclidean distance for each point and insert it into the min heap. We then pop the top k elements from the heap to get the k closest points to the origin.

Create a min heap to store points based on their distance from the origin
Calculate the distance for each point and insert it into the min heap
Pop the top k elements from the heap to get the k closest points

Time complexity: O(n log k) where n is the number of points Space complexity: O(k)

Solution Code

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

        for (int[] point : points) {
            minHeap.offer(point);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[][] result = new int[k][2];
        int i = 0;
        while (!minHeap.isEmpty()) {
            result[i] = minHeap.poll();
            i++;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 973 (K Closest Points to Origin)?

This page provides optimized solutions for LeetCode problem 973 (K Closest Points to Origin) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 973 (K Closest Points to Origin)?

The time complexity for LeetCode 973 (K Closest Points to Origin) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 973 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 973 in Java, C++, or Python.

Back to LeetCode Solutions