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
Problem: 149. Max Points on a Line
Problem Link: leetcode.com/problems/max-points-on-a-line/
Companies Asked: Amazon, Google, Oracle, LinkedIn, Sprinklr
Approach:
According to basic geometry, three points will be on the same line if their Slopes are equal.
Slope between any two point (x, y), (x1, y1) can be calculated by m = (y - y1) / (x - x1)
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.
Now, traverse through the given points.
For a point (x, y) calculate slopes for the other (x1, y1).
Count the number of the same slopes in a hashmap.
Take max for each counting.
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;
}
};