149. Max Points on a Line

• Difficulty: Hard

• Topics: Hash Table, Math

• Similar Questions:

  • Line Reflection

Problem:

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solutions:

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int ret = 0;
        for (int i = 0; i < points.size(); ++i) {
            map<pair<int, int>, int> lines;
            int verticleCount = 0; // dedicated 
            int horizonCount = 0; // dedicated
            int selfCount = 1;
            for (int j = i + 1; j < points.size(); ++j) {
                if (points[j][0] == points[i][0] && points[j][1] == points[i][1])   ++selfCount;
                else if (points[j][0] == points[i][0])  ++verticleCount;
                else if (points[j][1] == points[i][1])  ++horizonCount;
                else {
                    ++lines[simplify(points[j][1] - points[i][1], points[j][0] - points[i][0])];
                }
            }

            int count = max(verticleCount, horizonCount);
            for (auto line : lines) {
                count = max(count, line.second);
            }

            count += selfCount;

            ret = max(ret, count);
        }

        return ret;
    }

    pair<int, int> simplify(int a, int b) {
        if (a < 0) { // every a should be not negtive
            a = -a;
            b = -b;
        }

        int divisor = gcd(a, abs(b)); // both number should be positive
        return {a/divisor, b/divisor};  // not times sign
    }

    int gcd (int a, int b) {

        if (a < b)  return gcd(b, a);
        if (b == 0) return a;           
        return gcd(b, a%b);
    }
};