Advertisement
imashutosh51

Maximum points on a line

Oct 29th, 2022
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. /*
  2. Logic:
  3. We can find the slope of line from two points by slope=(y2-y1)/(x2-x1).
  4. We will iterate through the points and consider all the pairs of points.
  5. There is one temporary map which will store the slope count for every pairs
  6. for each ith iteration and finally pairs with maximum points of same slope
  7. will be the answer.
  8. There is one catch that when line will be vertical then (x2-x1) ie. denominator
  9. will be 0 so we are managing vertical lines using a temporary variable.
  10. */
  11.  
  12. class Solution {
  13. public:
  14.     int maxPoints(vector<vector<int>>& points) {
  15.         int n=points.size();
  16.         int ans=0;
  17.         for(int i=0;i<n;i++){
  18.             unordered_map<double,int> mp;
  19.             int vertical=0;
  20.             for(int j=i+1;j<n;j++){
  21.                 if(points[j][0]-points[i][0] ==0){vertical++;ans=max(ans,vertical);continue;}
  22.                 double slope= (double)(points[j][1]-points[i][1])/(points[j][0]-points[i][0]+1.0-1.0);
  23.                
  24.                 mp[slope]++;
  25.                 ans=max(ans,mp[slope]);
  26.             }
  27.              mp.clear();
  28.            
  29.         }
  30.         return ans+1;
  31.     }
  32. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement