Fast C# solution.


  • 0
    N

    Here is my C# solution:

    0_1473108869675_runtime.jpg

    public class Solution {

    public int MaxPoints(Point[] points)
    {
        return MaxPoints(points, 0, 0);
    }
    
    
    public int MaxPoints(Point[] points, int index, int maxNumberOfPoints)
    {
        if (points.Length == 0)
        {
            return 0;
        }
    
        if( points.Length - index <= maxNumberOfPoints)
        {
            return maxNumberOfPoints;
        }
        
        double maxKey = 0;
        int duplicatePoints = 0;
    
        Dictionary<double, int> slopeToCountMap = new Dictionary<double, int>();
        for (int i = index; i < points.Length; i++)
        {
            if (areEqual(points[i], points[index]))
            {
                duplicatePoints++;
            }
            else
            {
                double slope = getSlope(points[index], points[i]);
                maxKey = incrementSlopeCount(slope, slopeToCountMap, maxKey);
            }
        }
    
        if (slopeToCountMap.ContainsKey(maxKey))
        {
            maxNumberOfPoints = Math.Max(slopeToCountMap[maxKey] + duplicatePoints, maxNumberOfPoints);
        } else
        {
            maxNumberOfPoints = Math.Max(duplicatePoints, maxNumberOfPoints);
        }
    
        return MaxPoints(points, index + 1, maxNumberOfPoints);
    }
    
    private bool areEqual(Point a, Point b)
    {
        return a.x == b.x && a.y == b.y;
    }
    
    private double getSlope(Point left, Point right)
    {
        double dx = left.x - right.x;
        double dy = left.y - right.y;
    
        double slope = 0;
        if (dy != 0)
        {
            slope = dx / dy;
        }
    
        return slope;
    }
    
    private double incrementSlopeCount(double slope, Dictionary<double, int> slopeToCountMap, double maxKey)
    {
        if (slopeToCountMap.ContainsKey(slope))
        {
            slopeToCountMap[slope] += 1;
        }
        else
        {
            slopeToCountMap[slope] = 1;
        }
    
        if ((!slopeToCountMap.ContainsKey(maxKey)) || (slopeToCountMap[slope] >= slopeToCountMap[maxKey]))
        {
            maxKey = slope;
        }
    
        return maxKey;
    }
    

    }


Log in to reply
 

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