# 16ms/28ms C++ Solutions with Explanations

• This problem has a naive idea, which is to traverse all possible pairs of two points and see how many other points fall in the line determined by them. This idea is of `O(n^3)` time complexity and will meet TLE.

Well, let's focus on lines instead of pairs of points. Could we just find out how many points fall in all possible lines? The answer is yes. Remember that a line is determined by its slope and intercept. In fact, if two lines with the same slope share a common point, then they are just the same line. So to determine a line, we need its slope and a point.

Now comes the idea to solve this problem. We start from a specific point `p`, and compute all the slopes of the lines between `p` and the remaining points. Then those with the same slopes will be the same line. We can find out the maximum number of points fall on a line containing `p`. We exhaust all possible `p`'s and record the largest number we have seen. This number is just answer.

Well, there are still two special cases to handle:

1. Duplicate points: a pair of duplicate points give no determined line, so we just count the number of duplicates and add them to the result.
2. Vertical lines: the slope of these lines is infinity mathematically. We simply set it to be `INT_MAX` in the following code.

Now we have the following code, using an `unordered_map<float, int> slopes` to record how many points fall in the line of a specific slope and containing `points[i]`. Since all the operations of `unordered_map` is `O(1)`, this code is of `O(n^2)` complexity.

``````class Solution {
public:
int maxPoints(vector<Point>& points) {
unordered_map<float, int> slopes;
int maxp = 0, n = points.size();
for (int i = 0; i < n; i++) {
slopes.clear();
int duplicate = 1;
for (int j = i + 1; j < n; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
duplicate++;
continue;
}
float slope = (points[j].x == points[i].x) ? INT_MAX :
(float)(points[j].y - points[i].y) / (points[j].x - points[i].x);
slopes[slope]++;
}
maxp = max(maxp, duplicate);
for (auto slope : slopes)
if (slope.second + duplicate > maxp)
maxp = slope.second + duplicate;
}
return maxp;
}
};
``````

Well, since the representation of floating point numbers is sometimes inaccurate, we may use a more safer way to represent the slope (`dy / dx`), which is to record `dx` and `dy` in a `pair<int, int>`. However, once we use `pair<int, int>` for the key of the map, we cannot use an `unordered_map` since `pair<int, int>` is unhashable. We now change to `map` and the time complexity becomes `O(n^2logn)`. Also, since `dy = 4, dx = 2` and `dy = 8, dx = 4` represents the same slope, we need to divide both of them by their gcd first.

The code is as follows. The logic is the same of the one above, just introducing `pair` and `gcd`.

``````class Solution {
public:
int maxPoints(vector<Point>& points) {
map<pair<int, int>, int> slopes;
int maxp = 0, n = points.size();
for (int i = 0; i < n; i++) {
slopes.clear();
int duplicate = 1;
for (int j = i + 1; j < n; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
duplicate++;
continue;
}
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int dvs = gcd(dx, dy);
slopes[make_pair(dx / dvs, dy / dvs)]++;
}
maxp = max(maxp, duplicate);
for (auto slope : slopes)
if (slope.second + duplicate > maxp)
maxp = slope.second + duplicate;
}
return maxp;
}
private:
int gcd(int num1, int num2) {
while (num2) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
};``````

• (dx=-2, dy=3) and (dx=2, dy=-3) will be treated as two lines in your code? How about (dx=-2, dy=-3) and (dx=2, dx=3)?

• [[0,0],[1,2147483647],[0,1]] would fail.

[[0,0],[1,2147483647],[0,1]]

3

2

• @jianchao.li.fighter Two improvements

• We can still use unordered_map as long as we provide our own hash : )
``````struct myhash {
size_t operator()(const pair<int,int>& p) const {
return p.first ^ p.second * 3;
}
};
``````
• More concise GCD method
``````int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
``````

• @jianchao-li-fighter The first version cannot pass with the input [0,0], [94911151, 94911150], [94911152, 94911151], which outputs the wrong answer 3. Is this because the using of "float" as the map key, which causes problem when calculating the slope? Thanks a lot.

• What if you have two different vertical lines with different x, are you putting all of them in to the INT_MAX bin?

• @jianchao.li.fighter Great concise code! So I thought I was being clever, and used a string instead of a pair to store the key, so that I can use unordered_map, instead of map. However, my supposedly O(n^2) code took 20ms vs the 6ms of your O(n^2logn) code. If anyone knows why, would love to hear your thoughts, thanks!

``````class Solution {
public:
int maxPoints(vector<Point>& points) {
int div, res=0, n=points.size();
unordered_map<string,int> slopes;

for (int i=0; i<n; i++) {
int self=1;
slopes.clear();
slopes["dummy"]=0; // takes care the case of a single point

for (int j=i+1; j<n; j++) {
Point &a=points[i], &b=points[j];

if (a.x==b.x && a.y==b.y) self++;
else if (a.x==b.x) slopes["vertical"]++;
else {
div=gcd(a.y-b.y,a.x-b.x);
string key=to_string((a.y-b.y)/div)+' '+to_string((a.x-b.x)/div);
slopes[key]++;
}
}

for (auto p:slopes) res=max(res,p.second+self);
}

return res;
}
private:
int gcd(int num1, int num2) {
int temp;
while (num2) {
temp=num2;
num2=num1%num2;
num1=temp;
}
return num1;
}
};
``````

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