max-points-on-a-line.md

149. Max Points on a Line

Hard

---

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:

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

Example 2:

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.

Solution:

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        unordered_map<double,int> mp;
        int ans=1;
        for(int i=0;i<points.size();i++){
            for(int j=i+1;j<points.size();j++){
                double slope=DBL_MAX;
                if(points[i][0]!=points[j][0])
                    slope=(0.0+points[j][1]-points[i][1])/(0.0+points[j][0]-points[i][0]);
                mp[slope]++;
                ans=max(ans,mp[slope]+1);
            }
            mp.clear();
        }
        return ans;
    }
};