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.

https://leetcode.com/problems/max-points-on-a-line/

Solution:

public class Solution { public int maxPoints(Point[] points) { if (points.length == 0) { return 0; } int n = points.length; int max = 0; Map map = new HashMap<>(); for (int i = 0; i < n; i++) { int duplicate = 1, vertical = 0; // note that duplicate is initially 1 for (int j = i+1; j < n; j++) { Point a = points[i]; Point b = points[j]; if (a.x == b.x) { if (a.y == b.y) { duplicate++; } else { vertical++; } } else { double slope = getSlope(a, b); if (!map.containsKey(slope)) { map.put(slope, 1); } else { map.put(slope, map.get(slope) + 1); } } } for (Integer count : map.values()) { max = Math.max(max, count+duplicate); } max = Math.max(max, vertical+duplicate); map.clear(); } return max; } public double getSlope(Point a, Point b) { if (a.y == b.y) { return 0.0; } // this is necessary return 1.0 * (a.y - b.y) / (a.x - b.x); } }