973. K Closest Points to Origin — LeetCode(Python)
I got you!
Problem:
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 (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
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 points 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:
1 <= k <= points.length <= 104-104 < xi, yi < 104
Solution:
1. Dynamic Heap Creation —
Explanation —
We can use a heap data structure to solve this problem.
We iterate over all points in the list points. While doing so, we calculate the distance a given point is away from the origin.
Then, a tuple containing this distance and the point is pushed into our heap.
Note that while pushing into the heap, the negative of the distance d is considered. This is because we are trying to create a maxheap, since we need to pop out the larger elements so that the points closest to the origin are left inside the heap.
If the number of elements in the heap is greater than k, we pop an element from the heap.
Finally, we return the coordinates that are left in the heap as they are the coordinates with the least amount of distance.
Time and Space Complexity —
The creation of a heap is a linear time operation.
However, pushing and popping from the heap are logarithmic time operations. This changes the overall time complexity of our code.
Also, we require a linear amount of extra space to store our heap.
Thus, if n is the length of the array nums,
Time Complexity: O(nlogn)
Space Complexity: O(k)
As we can see, this algorithm is no better than just sorting the coordinates by distance. So, we improve upon this approach in the next part of the solution.
2. Popping After heapify —
Explanation —
In this case, we first store all the coordinates along with their distance from the origin in a new list.
We then, heapify this list creating a minheap.
Finally, we pop out the first k elements from the heap, store it in a result array and return the result.
Time and Space Complexity —
Creating the list and heapifying it is a linear time operation.
And pushing and popping from the heap is a logarithmic time operation.
Also, we require a linear amount of auxiliary space to store the heap.
Thus, if n is the length of the list points,
Time Complexity: O(n + klogn)
Space Complexity: O(n)
Even though we took a hit on our space complexity, our runtime improved significantly.
