# 149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

img 
Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

img 
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • All the points are unique.

# Answer

  1. The obvious way is to make a map from lines to their points, this will requires O(n2)O(n^2) time complexity since we are going through all lines by connecting every point with all other points. Space complexity would also be O(n2)O(n^2) because we are storing all lines and corresponing points.

    (Using double to represent slope k here is actually not optimal due to the nature of floating points, but it'll work for this question)

    class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if (points.size() <= 1) {
            return points.size();
        } 
        // y=kx+b
        // (k, (b, points set))
        unordered_map<double, unordered_map<double, unordered_set<vector<int>*>>> lineCounts;
        // for x=... lines
        unordered_map<int, unordered_set<vector<int>*>> xLineCounts;
        for (int i = 0; i < points.size() - 1; i++) {
            for (int j = i + 1; j < points.size(); j++) {
                vector<int> &p1 = points[i], &p2 = points[j];
                if (p1[0] == p2[0]) {
                    if (xLineCounts.find(p1[0]) == xLineCounts.end()) {
                        xLineCounts[p1[0]] = unordered_set<vector<int>*>();
                    }
                    xLineCounts[p1[0]].insert(&p1);
                    xLineCounts[p1[0]].insert(&p2);
                } else {
                    double k = (double)(p1[1] - p2[1]) / (p1[0] - p2[0]);
                    double b = (double)p1[1] - k * p1[0];
                    if (lineCounts.find(k) == lineCounts.end()) {
                        lineCounts[k] = unordered_map<double,unordered_set<vector<int>*>>();
                    } 
                    if (lineCounts[k].find(b) == lineCounts[k].end()) {
                        lineCounts[k][b] = unordered_set<vector<int>*>();
                    }
                    lineCounts[k][b].insert(&p1);
                    lineCounts[k][b].insert(&p2);
                }
            }
        }
        int maxVal = 0;
        for (auto &kb : lineCounts) {
            for (auto &bv : kb.second) {
                // cout << kb.first << ' ' << bv.first << ' ' << bv.second.size() << endl;
                maxVal = max(maxVal, (int)bv.second.size());
            }
        }
        for (auto & xv: xLineCounts) {
            maxVal = max(maxVal, (int)xv.second.size());
        }
        return maxVal;
    }
};

    Runtime: 44 ms

    Memory: 20.5 MB

Answer