K Closest Points To Origin Leetcode Problem 973 [Python Solution]
How would you like to learning solving K Closest Points To Origin Leetcode problem with efficiency?
This is a medium difficulty problem that falls under the category of Heap/Priority Queue.
The problem requires finding the k closest points to the origin (0,0) on the X-Y plane from a given array of points.
Problem Overview
Let’s start by understanding the problem statement.
Given an array of points where each point is represented as [x, y], and an integer k, our task is to return the k closest points to the origin.
The distance between two points in the X-Y plane is calculated using the Euclidean distance formula:
Distance = √((x1 – x2)^2 + (y1 – y2)^2)
The key points to remember are:
- We need to find the k closest points.
- The order of the points in the output does not matter.
- The solution is guaranteed to be unique.
Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: 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.
We only want the closest k = 1 point from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints
The problem comes with the following constraints:
- 1 <= k <= points.length <= 104
- -104 <= xi, yi <= 104
Now, let’s dive into the efficient Python solution to this problem.
Efficient Python Code Solution
def kClosest(points: List[List[int]], k: int) -> List[List[int]:
minHeap = []
for x, y in points:
dist = (x ** 2) + (y ** 2)
minHeap.append((dist, x, y))
heapq.heapify(minHeap)
res = []
for _ in range(k):
_, x, y = heapq.heappop(minHeap)
res.append([x, y])
return res
Now, let’s break down this code step by step.
1. Creating a Min Heap
The first step is to create an empty min heap (priority queue) using the heapq
module.
In this min heap, we will store tuples containing three values:
- The square of the Euclidean distance (dist) for each point.
- The x-coordinate (x) of the point.
- The y-coordinate (y) of the point.
We calculate the distance squared (dist) for each point to avoid the need for square root calculations, which would be less efficient.
We add these tuples to the min heap.
2. Populating the Min Heap
Next, we loop through all the points in the input list points
.
For each point [x, y]
, we calculate the squared distance using (x ** 2) + (y ** 2)
.
We then create a tuple (dist, x, y)
and add it to the min heap.
The min heap will automatically organize these tuples based on their distances, ensuring that the tuple with the smallest distance is at the top.
3. Popping from the Min Heap
Now, we need to retrieve the k closest points.
We pop from the min heap k times.
In each iteration, we extract the tuple with the smallest distance from the heap.
The heapq.heappop()
operation retrieves and removes the smallest element from the min heap.
We collect the x and y coordinates and append them to the result list.
4. Returning the Result
Once we have collected k closest points in the result list, we return this list as the final output.
The order of the points in the result list does not matter, as the problem statement allows any valid order.
Time and Space Complexity
Let’s analyze the time and space complexity of this solution.
Time Complexity:
- The loop to calculate distances and create tuples for all points takes
O(n)
time, where n is the number of points. - The
heapify
operation takesO(n)
time. - Popping k times from the min heap takes
O(k * log(n)
) time. - Overall, the time complexity is
O(n + n + k * log(n)
), which simplifies toO(n + k * log(n)
).
Space Complexity:
- The space complexity is determined by the min heap, which stores all points.
It requires O(n)
space.
Reasoning Behind Our Approach
Our approach is based on using a min heap (priority queue) to efficiently find the k closest points to the origin.
The key idea is to avoid sorting the entire list of points, which would take O(n * log(n)
) time, and instead focus on finding just the k smallest distances.
We use the squared distance for comparison to avoid square root calculations, which simplifies the code and improves efficiency.
By maintaining a min heap, we can quickly retrieve the k closest points in O(k * log(n)
) time, where n is the number of points.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Conclusion
In this blog post, we’ve solved the K Closest Points To Origin problem on LeetCode efficiently using a min heap.
We’ve explained the problem, provided a Python solution, and analyzed the time and space complexity of our approach.
If you found this post helpful, please consider liking and subscribing to support our our platform.
If you have any questions, suggestions, or comments, feel free to share them in the comments section below.
You can access the original problem on LeetCode using the following link: K Closest Points to Origin – LeetCode.
Happy coding and keep exploring the fascinating world of algorithms and data structures!