https://discuss.leetcode.com/topic/101/k-closest-points-to-a-starting-point-in-cartesian-plane
Given a set of points in a cartesian plane, and a start point , find the k closest points to the starting point.
Points = [(1,2),(2,3),(4,6),(7,9)]
Start Point = (2,2)
Start Point = (2,2)
Find 2 closest points to start point.
Calculate all the distance with O(n) seems unavoidable.
And a set with size of k to find the top k.
And a set with size of k to find the top k.
Time complexity: O(n) + O(n * logk)
Space complexity: O(k)
Space complexity: O(k)
What are the constraints of the problem? Are there many queries for different K?
If problem is isolated one, you have a set of points, and fixed start point, the approach above is very optimal.
But if we have a set of points and a lot of queries , where start point , K change, maybe it is better to use Kd tree for 2d. With Kd tree time complexity is klog(n) for query and nlog(n) for building the tree.Space complexity O(n).With Kd tree we don't need even to calculate euclidean distance
If problem is isolated one, you have a set of points, and fixed start point, the approach above is very optimal.
But if we have a set of points and a lot of queries , where start point , K change, maybe it is better to use Kd tree for 2d. With Kd tree time complexity is klog(n) for query and nlog(n) for building the tree.Space complexity O(n).With Kd tree we don't need even to calculate euclidean distance
This is a great follow up! If there are a lot of queries where start point or value of k change, or even when the set of points can be added, then solving it efficiently should use space partitioning algorithms like kd-tree to reduce the search space to a section in the cartesian space.
