149. Max Points on a Line

First, let's talk about mathematics.

How to determine if three points are on the same line?

The answer is to see if slopes of arbitrary two pairs are the same.

Second, let's see what the minimum time complexity can be.

Definitely, O(n^2). It's because you have to calculate all slopes between any two points.

Given point A, we need to calculate all slopes between A and other points. There will be three cases:

1. Some other point is the same as point A.

2. Some other point has the same x coordinate as point A, which will result to a positive infinite slope.

3. General case. We can calculate slope.

We can store all slopes in a hash table. And we find which slope shows up mostly. Then add the number of same points to it. Then we know the maximum number of points on the same line for point A.

1. use hashmap, 計算相同的斜率的 count

2. 重合的點要個別計算, 最後加到結果 （題目後來有改過, 現在所有點都是 unique 的

3. dy/dx 計算斜率, 需要除法, 這是不安全的, 用 double 存斜率是不可靠的, 精度不夠, 所以不真的計算 slope,

4. 但不計算 slope 的話, 需要先算出 dy, dx 的 GCD,

dy, dx 如果是互質, 都是最簡分數, 那算出來的斜率才會是 unique 的, 要達到互質: 做約分, 所以需要 GCD

int a = dy/ gcd(dy, dx)

int b = dx/ gcd(dy, dx)

然後直接拿 a, b 當成 key 來用, 不用計算 slope! 這裡直接拿 a +"," + b 當 hashmap key

如果用 double 像這樣, 差距微乎其微, double 計算出來的斜率會是一樣的

為什麼可以用斜率來求呢？ 三點想要共線 (a, b,c), 固定一個點, 一定有兩對斜率是一樣的(a,b 斜率 跟 a, c 斜率一樣), 所以需要兩兩去比較, 所以 time complexity 會是 O(n^2)

T: O(n^2), n is number of points

S: O(n)

有計算重複的點的版本:

class Solution {
    public int maxPoints(int[][] points) {
        int m = points.length;
        Map<String, Integer> map;
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            map = new HashMap<>();
            int max = 0;
            int duplicate = 0;
            for (int j = i+1; j < m; j++) {
                int deltaX = points[j][0] - points[i][0];
                int deltaY = points[j][1] - points[i][1];
                if (deltaX == 0 && deltaY == 0) {
                    duplicate++;
                    continue;
                }
                
                int gcd = gcd(deltaX, deltaY);
                int dx = deltaX/gcd;
                int dy = deltaY/gcd;
                
                String key = dx + "," + dy;
                map.put(key, map.getOrDefault(key, 0)+1);
                max = Math.max(max, map.get(key));
            }
            res = Math.max(res, max + duplicate + 1); // 這個 +1. 是 i 固定的那一個點
        }
        return res;
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}

no duplicate:

class Solution {
    public int maxPoints(int[][] points) {
        int m = points.length;
        Map<String, Integer> map;
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            map = new HashMap<>();
            int max = 0;
            for (int j = i+1; j < m; j++) {
                int deltaX = points[j][0] - points[i][0];
                int deltaY = points[j][1] - points[i][1];
                
                int gcd = gcd(deltaX, deltaY);
                int dx = deltaX/gcd;
                int dy = deltaY/gcd;
                
                String key = dx + "," + dy;
                map.put(key, map.getOrDefault(key, 0)+1);
                max = Math.max(max, map.get(key));
            }
            res = Math.max(res, max + 1); // 這個 +1. 是 i 固定的那一個點
        }
        return res;
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}