Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table Math

-------------------------------------
-------------------------------------

Set point(i,j) as the base, calculate the slope between all the other points and the base point(i,j). Then check how many points have the same slope and therefore we can find the temporal max number. Repeat each point as the base and in the final we can find out the global maximal.
Note: the base point should be counted into as well;
          the duplicate points of point(i,j) should be also counted into.


/////////////////////////////////////////////////
//whole project

#include "stdafx.h"

# include <cstdlib>

#include <iostream>     // std::cout

#include <algorithm>    // std::sort

#include <vector>       // std::vector

# include <map>         // std::map

# include <unordered_map>

# include <string>

#include <bitset>

#include <ctype.h>

using namespace std;

 //Definition for a point.

 struct Point {

     int x;

     int y;

     Point() : x(0), y(0) {}

     Point(int a, int b) : x(a), y(b) {}

 };

 class Solution {

 public:

        int maxPoints(vector<Point>& points) {

               //check input

               if (points.size()<3)return points.size();

               //loop

               map<float, int> mSlop;

               int maxNum = 0, len = points.size();

               float slop = 0;

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

                      int count = 0;

                      for (int j = 0; j<len; j++){

                            if (i != j){

                                   if (points[j].y == points[i].y && points[j].x == points[i].x){

                                          count++;

                                          continue;

                                   }

                                   slop = points[j].x - points[i].x == 0 ? INT_MAX : (points[j].y - points[i].y) / (points[j].x - points[i].x);

                                   mSlop[slop]++;

                            }

                      }

                      //find the current max in current loop

                      int curMax = 0;

                      for (map<float, int>::iterator it = mSlop.begin(); it != mSlop.end(); it++){

                            curMax = max(curMax, it->second);

                      }

                      curMax += count;

                      //the max up to now

                      maxNum = maxNum>curMax ? maxNum : curMax;

                      mSlop.clear();

               }

               maxNum++;//itself

               return maxNum;

        }

 };

int main(int argc, char *argv[])

{

       Point *one1 = new Point(-4,-1);

       Point *one2 = new Point(-7,7);

       Point *one3 = new Point(-1,5);

       Point *one4 = new Point(9,-25);

       vector<Point> in;

       in.push_back(*one1);

       in.push_back(*one2);

       in.push_back(*one3);

       in.push_back(*one4);

       Solution s;

       int f = s.maxPoints(in);

}