Ac solution code


  • 0

    The basic idea is using HashMap to count the points having the same gradient to points[i].

    Hints:

    1. Should use double, instead of float;

    2. Pay attention to the duplicate points with same coordinates as points[i]: need to add duplicates to the amount of points grouped by the gradient.

    Time = O(n^2); Space = O(n)

     public int maxPoints(Point[] points) {
        int n = points.length, max = (points.length == 0) ? 0 : 1;
        for (int i = 0; i < n; i++) {
            Map<Double, Integer>map = new HashMap<Double, Integer>();// <gradient, amount>
            map.put(Double.MIN_VALUE, 1);// points[i] itself
            int duplicates = 0;// The same point as points[i]
            for (int j = i + 1; j < n; j++) {// Find max points having the same gradient to points[i]. NOTE: gradient(point[i], point[j]) = gradient(point[j], point[i]), so j starts from i+1.
                if (points[i].x == points[j].x && points[i].y == points[j].y)  {
                    duplicates++; 
                    continue;
                }
                double gradient = Double.MAX_VALUE;
                if (points[j].x != points[i].x) 
                    gradient = 0 + (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);                 
    
                int count = map.containsKey(gradient) ? map.get(gradient) : 1;              
                map.put(gradient, ++count);             
            }           
            for (Integer number : map.values())// Compare the number of the points having same gradient
                max = Math.max(max, number + duplicates);
        }
        return max;
    }

Log in to reply
 

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