149. Max Points on a Line

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
       public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) return 0;


        int max = 0;
        for (int j = 0; j < points.length; j++) {
            Map<Double, Integer> map = new HashMap<>();
            Point pivot = points[j];

            int special= 0;
            int same = 0;
            for (int i = 0; i < points.length; i++) {
                if (pivot.x == points[i].x && pivot.y == points[i].y) {
                    same++;
                } else if (pivot.x == points[i].x) {
                    special++;
                } else {
                    double slope = slope(pivot, points[i]);
                    map.merge(slope, 1, (a, b) -> a + b);
                }
            }

            for (Integer in : map.values()) {
                if (special < in) {
                    special = in;
                }
            }

            max = special + same > max ? special + same : max;
        }

        return max;
    }

    public double slope(Point point1, Point point2) {
        return (point1.y - point2.y) / (float) (point1.x - point2.x);
    }

}