149. 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.

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

int gcd(int num1, int num2) {
    while (num2 != 0) {
        int tmp = num2;
        num2 = num1 % num2;
        num1 = tmp;
    }
    return num1;
}
int maxPoints(vector<vector<int>>& points) { // time: O(n^2 * log(n^2)); space: O(n^2)
    map<pair<int, int>, int> slopes;
    int n = points.size(), res = 0;
    for (int i = 0; i < n; ++i) {
        slopes.clear();
        int duplicate = 1;
        for (int j = i + 1; j < n; ++j) {
            if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
                ++duplicate;
                continue;
            }
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            int dvs = gcd(dx, dy);
            ++slopes[{dx / dvs, dy / dvs}];
        }
        res = max(res, duplicate); // handle corner cases such as all input points are the same points
        for (auto& slope : slopes) {
            res = max(res, slope.second + duplicate);
        }
    }
    return res;
}