Problem description:

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

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:

^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:

^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

Solution:

Calculate slope for two points, use hash table to store the points on same slope.

Might have vertical or horizontal line.

Might have duplicate points.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        def helper(currentPoint, points):
            slopes,duplicates,ans = {},0,0
            x1, y1 = currentPoint
            for x2, y2 in points:
                # If the points are same inc duplicate counter
                if x1 == x2 and y1 == y2:
                    duplicates += 1
                # else find the slop and add in dic
                else:
                    slope = (x2 - x1) / (y2 - y1) if y2 != y1 else 'inf'
                    count = slopes.get(slope, 0) + 1
                    slopes[slope] = count
                    ans = max(ans, count)
            return ans + 1 + duplicates
        
        if len(points) < 3:
            return len(points)
        # if vertical or horizontal line
        if len(set([i[0] for i in points])) == 1 or len(set([i[1] for i in points])) == 1:
            return len(points)
        ans = 0
        while points:
            currentPoint = points.pop()
            ans = max(ans, helper(currentPoint, points))
        return ans

basic solution:
Calculate slope for two points to find whether if they are on the same line, the solution is O(n^2). First of all, we can divide the points into three groups, exact same point, one the same vertical, or general slope. However, this can not pass one test case, so need to improve based on it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Failed on case: [[0,0],[94911151,94911150],[94911152,94911151]]
int maxPoints(vector<Point> &points) {
    int result = 0;
    for(int i = 0; i < points.size(); i++){
        int samePoint = 1;
        unordered_map<double, int> map;
        for(int j = i + 1; j < points.size(); j++){
            if(points[i].x == points[j].x && points[i].y == points[j].y){
                samePoint++;
            }
            else if(points[i].x == points[j].x){
                map[INT_MAX]++;
            }
            else{
                double slope = double(points[i].y - points[j].y) / double(points[i].x - points[j].x);
                map[slope]++;
            }
        }
        int localMax = 0;
        for(auto it = map.begin(); it != map.end(); it++){
            localMax = max(localMax, it->second);
        }
        localMax += samePoint;
        result = max(result, localMax);
    }
    return result;
}

Previous solution have a major problem. First, the slope is not concise because if may exceed the number that double can express. Therefore, we can find the greatest common divisor(GCD) to avoid the issue. We calculate every GCD and use it to divide the dx and dy.
For example: if we have [8,4], [4,2], [2,1] to be our slope, these three slopes will be counted into one map value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
    int maxPoints(vector<Point>& points) {
        /*
        1. divide the points into three groups:
            a. same point
            b. general slope
        2. count every slope for two points, O(n^2)
        3. the slope may have divided by zero problem, so use pair<int, int> to avoid that. In addition, find greatest common divisor to get accurate slope.
        4. add the same points to the localResult
        */
        int res = 0;
        for (int i = 0; i < points.size(); ++i) {
            map<pair<int, int>, int> m;
            int duplicate = 1;
            for (int j = i + 1; j < points.size(); ++j) {
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    ++duplicate; continue;
                } 
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int d = gcd(dx, dy);
                ++m[{dx / d, dy / d}];
            }
            res = max(res, duplicate);
            for (auto it = m.begin(); it != m.end(); ++it) {
                res = max(res, it->second + duplicate);
            }
        }
        return res;
    }
    int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
};

reference:
https://goo.gl/YRuLmT
http://www.cnblogs.com/grandyang/p/4579693.html