C# solution using Greatest Common Denominator


  • 0
    D

    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;
        }
    }
    


Log in to reply
 

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