# C# solution using Greatest Common Denominator

• I have a solution but a few notes ported from the Java Solution by R:

• I still don't quite understand while they allow duplicate points? For that, I down-voted this one, because it needs to be fixed in my opinion. Duplicate points don't exist in the 2D plane so this is a little weird. In fact, there is an infinite set of points in the 2D plane, but it is a set which implies each point is unique. To deal with this oddity, I labelled the variable "undefined" and just incremented it to pass the test cases (but, in reality, I wouldn't do that, but throw an InvalidOperationException or ArgumentException)

• We are try to find points on a line (y = mx + c), where m is the slope and c is constant. m is defined as deltaY/deltaX; c is derived from (y-y1=mx-x1) [e.g. (0,3) ==> c = 3]

• The GCD was a very clever work-around from tracking the slope. Any point on the same line will reduce down to the CGD (nice). Giving credit to the Java Solution by R (nice).

• The constant c was cleverly addressed, as well, by GCD for the same reason as above.

``````/// <summary>
/// Given a finite list (set would imply uniqueness) of points,
/// compute the max number of points that lie on a straight
/// line produced by the finite list; otherwise, max = infinity
/// </summary>
/// <example>
/// {{0,0},{0,0}} produces 2
/// {{0,0},{1,1},{1,-1}} = 2
/// </example>
public class Solution
{
private int GreatestCommonDenominator(int a, int b)
{
if (b == 0) return a;
else
return GreatestCommonDenominator(b, a % b);
}

public int MaxPoints(Point[] points)
{
//Track from x0 and y0
Dictionary<int, Dictionary<int, int>> slopeMap = new Dictionary<int, Dictionary<int, int>>();
int maxPoints = points.Length > 0 ? 1 : 0;

for(int i = 0; i < points.Length; i++)
{
slopeMap.Clear();
int localMax = 0, undefined = 0;
for (int j = i + 1; j < points.Length; j++)
{
int deltaX = points[j].x - points[i].x;
int deltaY = points[j].y - points[i].y;

if(deltaX == 0 && deltaY == 0)
{
undefined++;
continue;
}

int gcd = GreatestCommonDenominator(deltaY, deltaX);

if (gcd != 0)
{
deltaX /= gcd;
deltaY /= gcd;
}

if (!slopeMap.ContainsKey(deltaX))
{
slopeMap[deltaX] = new Dictionary<int, int>();
}

if (!slopeMap[deltaX].ContainsKey(deltaY))
{
slopeMap[deltaX][deltaY] = 1;
}
else
{
slopeMap[deltaX][deltaY]++;
}

localMax = Math.Max(localMax, slopeMap[deltaX][deltaY]);
}
maxPoints = Math.Max(maxPoints, localMax + undefined + 1);//+1 because I never added the initial point (x0,y0)
}

return maxPoints;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.