hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Max Points on a Line


  • Approach:

    1. According to basic geometry, three points will be on the same line if their Slopes are equal.

    2. Slope between any two point (x, y), (x1, y1) can be calculated by m = (y - y1) / (x - x1)

    3. Now while calculating slopes between any two points, if some points are on the same line then, their slope/elongation will be the same, although (y-y1) and (x-x1) may differ. Shown on the right side.

    4. Now, traverse through the given points.

    5. For a point (x, y) calculate slopes for the other (x1, y1).

    6. Count the number of the same slopes in a hashmap.

    7. Take max for each counting.

    8. Return maxCount + 1.


  • Time and Space Complexity:

      • Time Complexity: O(N^2)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:

int maxPoints(vector<vector<int>>& points) {

int n = points.size(), ans = 0;

for(int i=0; i<n; i++){

unordered_map<double, int>slope_cnt;

for(int j=i+1; j<n; j++){

int x = points[i][0] - points[j][0];

int y = points[i][1] - points[j][1];

double slope = x ? (y * 1.0)/(x * 1.0) : INT_MAX * 1.0;

slope_cnt[slope]++;

ans = max(ans, slope_cnt[slope]);

}

}

return ans + 1;

}

};