# A c++ integer solution with sorting, caching, bounds checking

• This solution takes about 60 ms. The complexity is O(n^2).

1. It uses GCD of dx and dy to normalize the slope and to represent it with normalized (dx, dy), as mentioned in other solutions.
2. It sorts points on their x coordinates to put them into bins (of same x); points in each bin are sorted on their y coordinates. This transform defines the order in which I traverse lines and also generates several useful properties: (a) the closure box the all points; (b) number of points of vertical lines; (c) when I draw a non-vertical line from left to right, every vertical bin on its way adds no more than one unique point -- therefore I know the maximum number points a particular bin can add to a line; (d) when I traverse the plane from left to right, I know the upper bound of the number points the rest bins may add to a line.
3. I define lines with their first and second point from the left P0(x0, y0) and P1(x1, y1). I traverse all possible non-vertical lines in the following order: select P0 following sorted order (left to right, bottom to top) and select P1 from the bins right to P0's bin and also following the same order.
4. I extend a line from P1 to the right by crossing other bins. Checking if one bin contains a point on the given line is O(1) as bin is sorted.
5. With the sorting, I do the following two bounds checking and bail out earlier: (a) since I extend lines from left to right, I stop when it exceeds the closure box; (b) based on 2.c and 2.d, I stop when I see no enough points left to beat the existing result.
``````/**
* 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 GCD(int x, int y) const {
x = abs(x);
y = abs(y);
if(x == 0 && y == 0) return 1;
if(x == 0) return y;
if(y == 0) return x;
while(x%y) {
int newy = x%y;
x = y;
y = newy;
}
return y;
}

int maxPoints(vector<Point>& points) {
if(points.size() < 3) return points.size();
map<int, map<int, int> > sorted; // sort points with x coordiantes first, then with y coordinates
vector<pair<int, int> >xs;  // every element's first is a x coordinate; second is the upperbound
// of number points on non-vertical lines that are left to (x, *)
int maxCounter = 0;

Point minPt(numeric_limits<int>::max(), numeric_limits<int>::max());
Point maxPt(numeric_limits<int>::min(), numeric_limits<int>::min());

// sort points and find the closure box of all points
for(auto pt : points) {
if(pt.x < minPt.x) minPt.x = pt.x;
if(pt.y < minPt.y) minPt.y = pt.y;
if(pt.x > maxPt.x) maxPt.x = pt.x;
if(pt.y > maxPt.y) maxPt.y = pt.y;

sorted[pt.x][pt.y] = sorted[pt.x][pt.y]+1;
}
// fill xs
int acc = 0;
for(auto ptxit = sorted.rbegin(); ptxit != sorted.rend(); ++ptxit) {
int sum = 0;
int maxNum = 0;
for(auto y : ptxit->second) {
sum += y.second;
maxNum = max(y.second, maxNum);
}
acc += maxNum;
xs.push_back(make_pair(ptxit->first, acc));
maxCounter = max(sum, maxCounter);
}
reverse(xs.begin(), xs.end());

// cache element is accessed as cache[x][y][dx][dy]
// cache is organized with key (x, y, slope), where
// slope is represented with (dx, dy)
// if a point(x,y) has been checked on a line with slope (dx,dy)
// before, we don't need to check the line starting from this point of
// the same slope
map<int, map<int, map<int, set<int> > > > cache;

// find (x0, y0), the first point from left for a line
// enumerate from left to right for every possible x
for(auto x0it = xs.begin(); x0it != xs.end(); ++x0it) {
// the upper bound is already less than existing result
if(maxCounter >= x0it->second) break;
int x0 = x0it->first;
auto y0s = sorted[x0];
// for every point with same x0 from bottom to top
for(auto y0Item : y0s) {
// we have (x0, y0) now
int y0 = y0Item.first;
// find (x1, y1), the second left point on the line
// for every x1 greater than x0 from left to right
for(auto x1it = x0it + 1; x1it != xs.end(); ++x1it) {
// the upper bound is already less than existing result
if(maxCounter >= sorted[x0][y0] + x1it->second) break;
int x1 = x1it->first;
auto y1s = sorted[x1];
for(auto y1Item : y1s) {
// we have (x1, y1) and a line now
int y1 = y1Item.first;

// calculate normalized scope and represent it with (dx, dy) to avoid floating point
int dy = y1 - y0, dx = x1 - x0;
int gcd = GCD(dx, dy);
dy /= gcd; dx /= gcd;

// check if this point has been found on a line before
if(cache[x0][y0][dx].find(dy) != cache[x0][y0][dx].end()) continue;
int counter = sorted[x0][y0] + sorted[x1][y1];
// extend the line (x0, y0) (x1, y1) to the right, but only chek the x cooridates
// available in points
for(auto x2it = x1it + 1; x2it != xs.end(); ++x2it) {
// the upper bound is already less than existing result
if(maxCounter >= counter + x2it->second) break;
int x2 = x2it->first;
if((x2 - x0) % dx != 0) continue;  // if y2 of (x2, y2) on the current line is not an integer

int y2 = dy * (x2 - x0) / dx + y0; // this division won't result in fraction
if(y2 > maxPt.y || y2 < minPt.y) break;  // if it is alreay out of the closure box
auto y2s = sorted[x2];
if(y2s.find(y2) != y2s.end()) {
// found one
counter += sorted[x2][y2];
// cache the point with slope to avoid checking it again
cache[x2][y2][dx].insert(dy);
}
}
maxCounter = max(counter, maxCounter);
}
}
}
}

return maxCounter;
}

};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.