{ sung.codes }

by dance2die
Blog
← Go Back

K closest points to the origin in C#

Broken Post?Let me know

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

using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;
namespace Demo.LearnByDoing.Tests.RandomStuff.Glassdoor.Asana
{
/// <summary>
/// Reference: https://www.youtube.com/watch?v=eaYX0Ee0Kcg
/// MinHeap: https://www.youtube.com/watch?v=t0Cq6tVNRBA
/// </summary>
public class KClosePointsToOriginTest
{
[Fact]
public void TestHappyPath()
{
var points = new[]
{
(X: -2, Y: 4),
(X: 0, Y: -2),
(X: -1, Y: 0),
(X: 3, Y: 5),
(X: -2, Y: -3),
(X: 3, Y: 2),
};
var expected = new[]
{
(X: -2, Y: -3),
(X: -1, Y: 0),
(X: 0, Y: -2),
};
const int k = 3;
var actual = GetKClosestPointsToOrigin(k, points).ToList();
Assert.True(expected.SequenceEqual(actual));
}
private IEnumerable<(int, int)> GetKClosestPointsToOrigin(int k, (int X, int Y)[] points)
{
var pointToDistanceMap = BuildPointToDistanceMap(points);
var maxHeap = BuildMaxHeapMap(k, points);
for (int i = k; i < points.Length; i++)
{
// Replace the biggest with the current smallest
if (pointToDistanceMap[points[i]] < maxHeap.Peek().Distance)
{
maxHeap.Poll();
maxHeap.Add((points[i].X, points[i].Y, pointToDistanceMap[points[i]]));
}
}
while (maxHeap.HasItem())
{
var (x, y, _) = maxHeap.Poll();
yield return (x, y);
}
}
private Dictionary<(int, int), double> BuildPointToDistanceMap((int x, int y)[] points)
{
return points.ToDictionary(point => point, CalculateDistance);
}
private double CalculateDistance((int X, int Y) point) => Math.Sqrt(point.X * point.X + point.Y * point.Y);
private GenericMaxHeap<(int X, int Y, double Distance)> BuildMaxHeapMap(int k, (int X, int Y)[] points)
{
return points
.Take(k)
.Aggregate(new GenericMaxHeap<(int X, int Y, double Distance)>(new GenericMaxHeapComparer()),
(heap, point) =>
{
heap.Add((point.X, point.Y, CalculateDistance(point)));
return heap;
});
}
}
class GenericMaxHeapComparer: IComparer<(int X, int Y, double Distance)>
{
public int Compare((int X, int Y, double Distance) x, (int X, int Y, double Distance) y)
{
return (int) (x.Distance - y.Distance);
}
}
class GenericMaxHeap<T>
{
private T[] _items;
private int _capacity = 10;
private int _size;
private readonly IComparer<T> _comparer;
public GenericMaxHeap(IComparer<T> comparer)
{
_comparer = comparer;
_items = new T[_capacity];
}
public T Peek()
{
if (_size == 0) throw new ArgumentOutOfRangeException();
return _items[0];
}
public T Poll()
{
if (_size == 0) throw new ArgumentOutOfRangeException();
// move last item to the front and heapify down
var item = _items[0];
_items[0] = _items[_size - 1];
_size--;
HeapifyDown();
return item;
}
public bool HasItem() => _size > 0;
public void Add(T item)
{
EnsuareCapacity();
// Add it to the end and heapify up!
_items[_size] = item;
_size++;
HeapifyUp();
}
private void EnsuareCapacity()
{
if (_size < _capacity) return;
_capacity *= 2;
var items = new T[_capacity];
Array.Copy(_items, items, items.Length);
_items = items;
}
/// <summary>
/// Move the last item to as high as it can move up
/// </summary>
/// <remarks>
/// While there is a parent, which is less than the current item,
/// replace the parent with the current item by moving it up.
/// set the current index to that of the parent.
/// </remarks>
private void HeapifyUp()
{
var index = _size - 1;
while (HasParent(index) && _comparer.Compare(GetParentValue(index), _items[index]) < 0)
{
Swap(index, GetParentIndex(index));
index = GetParentIndex(index);
}
}
/// <summary>
/// Move the first item to as low as it can in the tree
/// </summary>
/// <remarks>
/// while the child exists (check left child only)
/// Get the larger child's index between Left & Right child
/// if the current item is bigger than the larger child's value, then break out of the loop
/// else swap the larger child with the current item
/// </remarks>
private void HeapifyDown()
{
var index = 0;
// Heap always starts from "left" child so no need to check for right child.
while (HasLeftChild(index))
{
int largestChildIndex = GetLeftChildIndex(index);
if (HasRightChild(index) && _comparer.Compare(GetRightChildValue(index), GetLeftChildValue(index)) < 0)
largestChildIndex = GetRightChildIndex(index);
if (_comparer.Compare(_items[index], _items[largestChildIndex]) < 0) break;
Swap(index, largestChildIndex);
index = largestChildIndex;
}
}
private bool HasParent(int childIndex) => GetParentIndex(childIndex) >= 0;
private bool HasLeftChild(int index) => GetLeftChildIndex(index) < _size;
private bool HasRightChild(int index) => GetRightChildIndex(index) < _size;
private int GetParentIndex(int childIndex) => (childIndex - 1) / 2;
private int GetLeftChildIndex(int index) => index * 2 + 1;
private int GetRightChildIndex(int index) => index * 2 + 2;
private T GetParentValue(int childIndex) => _items[GetParentIndex(childIndex)];
private T GetLeftChildValue(int index) => _items[GetLeftChildIndex(index)];
private T GetRightChildValue(int index) => _items[GetRightChildIndex(index)];
private void Swap(int index1, int index2) =>
(_items[index1], _items[index2]) = (_items[index2], _items[index1]);
}
}

View this gist on GitHub

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.

Resources