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.

Have you met this question in a real interview? 

Yes

Example

Given 4 points: (1,2), (3,6), (0,0), (1,3).

The maximum number is 3.

public class Solution {

    /**

     * @param points an array of point

     * @return an integer

     */

    public int maxPoints(Point[] points) {

        // Write your code here

        if(points == null || points.length == 0) return 0;

        int maxPoints = 0;

        for(int i = 0; i < points.length; i++){

            HashMap<Double, Integer> map = new HashMap<Double, Integer>();

            int samePoints = 1;

            int curMax = 0;

            for(int j = i+1; j < points.length; j++){

                double slope = 0;

                if(points[i].x == points[j].x && points[i].y == points[j].y){

                    samePoints++;

                    continue;

                }

                if(points[i].x - points[j].x == 0){

                    slope = Integer.MAX_VALUE;

                }else{

                    slope = (1.0 * (points[i].y - points[j].y)) / (points[i].x - points[j].x);

                }

                if(map.containsKey(slope)){

                    map.put(slope, map.get(slope) + 1);

                } else {

                    map.put(slope, 1);

                }

                

                curMax = Math.max(curMax, map.get(slope));

            }

            

            maxPoints = Math.max(curMax+samePoints, maxPoints);

            

        }

        return maxPoints;

    }

}