2018-11-14
K closest points to the origin in C#
problemsolving, programming, selfnote, algorithm
_Photo by Rick Mason on _Unsplash
Self note on what I did/learned today...
Today I implemented "K closest points to the origin" problem in C#.
Full Implementation
https://gist.github.com/dance2die/d8d1e851c6e26236eefe90dfa93a8830
Explanation
This problem requires you to calculate distances of all points and find the points with smallest distances.
To keep a track of smallest distances, MaxHeap (not MinHeap as you might expect initially) is used to keep the first kth distances.
As you go thru the rest of points (after kth position), if the current point's distance is smaller than the value in the MaxHeap, then replace that max value with the current point in the MaxHeap.
Eventually, you will be left with points with smallest distances.
k farthest points from the origin
One can also find the opposite using MinHeap instead of MaxHeap to find the farthest points from the origin.
Thoughts...
I've initially implemented MinHeap then implemented MaxHeap from scratch. To solve this problem, I had to implement MaxHeap yet again but instead of holding a plain "int" value, I made it more generic and passed a comparer object.
Implementing "Heap" data structure really solidified the understanding thereof and when it can come in handy.
Max/MinHeap is very underused IMO.