149. Max Points on a Line

  • 15.5%

https://leetcode.com/problems/max-points-on-a-line/#/description

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


https://discuss.leetcode.com/topic/6028/sharing-my-simple-solution-with-explanation

Sharing my simple solution with explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxPoints(vector<Point> &points) {
int result = 0;
for(int i = 0; i < points.size(); i++){
int samePoint = 1;
unordered_map<double, int> map;
for(int j = i + 1; j < points.size(); j++){
if(points[i].x == points[j].x && points[i].y == points[j].y){
samePoint++;
}
else if(points[i].x == points[j].x){
map[INT_MAX]++;
}
else{
double slope = double(points[i].y - points[j].y) / double(points[i].x - points[j].x);
map[slope]++;
}
}
int localMax = 0;
for(auto it = map.begin(); it != map.end(); it++){
localMax = max(localMax, it->second);
}
localMax += samePoint;
result = max(result, localMax);
}
return result;
}

First, let’s talk about mathematics.

How to determine if three points are on the same line?

The answer is to see if slopes of arbitrary two pairs are the same.

Second, let’s see what the minimum time complexity can be.

Definitely, O(n^2). It’s because you have to calculate all slopes between any two points.

Then let’s go back to the solution of this problem.

In order to make this discussion simpler, let’s pick a random point A as an example.

Given point A, we need to calculate all slopes between A and other points. There will be three cases:

  1. Some other point is the same as point A.

  2. Some other point has the same x coordinate as point A, which will result to a positive infinite slope.

  3. General case. We can calculate slope.

We can store all slopes in a hash table. And we find which slope shows up mostly. Then add the number of same points to it. Then we know the maximum number of points on the same line for point A.

We can do the same thing to point B, point C…

Finally, just return the maximum result among point A, point B, point C…


https://discuss.leetcode.com/topic/2709/c-o-n-2-solution-for-your-reference

Hint by @stellari

“For each point pi, calculate the slope of each line it forms with all other points with greater indices, i.e. pi+1, pi+2, …, and use a map to record how many lines have the same slope (If two lines have the same slope and share a common point, then the two lines must be the same one). By doing so, you can easily find how many points are on the same line that ends at pi in O(n). Thus the amortized running time of the whole algorithm is O(n^2).”

In order to avoid using double type(the slope k) as map key, I used pair (int a, int b) as the key where a=pj.x-pi.x, b=pj.y-pi.y, and k=b/a. Using greatest common divider of a and b to divide both a, b ensures that lines with same slope have the same key.

I also handled two special cases: (1) when two points are on a vertical line (2) when two points are the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
int maxPoints(vector<Point> &points) {

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

int result=0;

for(int i=0; i<points.size(); i++) {

map<pair<int, int>, int> lines;
int localmax=0, overlap=0, vertical=0;

for(int j=i+1; j<points.size(); j++) {

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

overlap++;
continue;
}
else if(points[j].x==points[i].x) vertical++;
else {

int a=points[j].x-points[i].x, b=points[j].y-points[i].y;
int gcd=GCD(a, b);

a/=gcd;
b/=gcd;

lines[make_pair(a, b)]++;
localmax=max(lines[make_pair(a, b)], localmax);
}

localmax=max(vertical, localmax);
}

result=max(result, localmax+overlap+1);
}

return result;
}

private:
int GCD(int a, int b) {

if(b==0) return a;
else return GCD(b, a%b);
}
};

https://discuss.leetcode.com/topic/12877/20-line-c-o-n-2-hashing-solution

The idea is straight forward. Calculate each slope between two points and handle two special cases: 1. vertical, 2. duplicate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maxPoints(vector<Point>& points)
{
if(points.size()<=2) return points.size();
int res=0;
for(int i=0;i<points.size()-1;i++) {
int numVertical=1,local=1,duplicate=0;
unordered_map<double,int> map;
for(int j=i+1;j<points.size();j++)
if(points[i].x==points[j].x) // special cases
if(points[i].y==points[j].y) // duplicate
duplicate++;
else // vertical
numVertical++;
else {
double slope=(points[i].y-points[j].y)*1.0/(points[i].x-points[j].x);
map[slope]==0?map[slope]=2:map[slope]++;
local=max(local,map[slope]);
}
local=max(local+duplicate,numVertical+duplicate);
res=max(res,local);
}
return res;
}
};

https://discuss.leetcode.com/topic/18447/16ms-28ms-c-solutions-with-explanations

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
}
};

https://discuss.leetcode.com/topic/21896/python-68-ms-code

Python 68 ms code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def maxPoints(self, points):
l = len(points)
m = 0
for i in range(l):
dic = {'i': 1}
same = 0
for j in range(i+1, l):
tx, ty = points[j].x, points[j].y
if tx == points[i].x and ty == points[i].y:
same += 1
continue
if points[i].x == tx: slope = 'i'
else:slope = (points[i].y-ty) * 1.0 /(points[i].x-tx)
if slope not in dic: dic[slope] = 1
dic[slope] += 1
m = max(m, max(dic.values()) + same)
return m

https://discuss.leetcode.com/topic/2979/a-java-solution-with-notes

A line is determined by two factors,say y=ax+b

If two points(x1,y1) (x2,y2) are on the same line(Of course).

Consider the gap between two points.

We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant

If a third point (x3,y3) are on the same line. So we must have y3=ax3+b

Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a

So we can use y0&x0 to track a line;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution{
public int maxPoints(Point[] points) {
if (points==null) return 0;
if (points.length<=2) return points.length;

Map<Integer,Map<Integer,Integer>> map = new HashMap<Integer,Map<Integer,Integer>>();
int result=0;
for (int i=0;i<points.length;i++){
map.clear();
int overlap=0,max=0;
for (int j=i+1;j<points.length;j++){
int x=points[j].x-points[i].x;
int y=points[j].y-points[i].y;
if (x==0&&y==0){
overlap++;
continue;
}
int gcd=generateGCD(x,y);
if (gcd!=0){
x/=gcd;
y/=gcd;
}

if (map.containsKey(x)){
if (map.get(x).containsKey(y)){
map.get(x).put(y, map.get(x).get(y)+1);
}else{
map.get(x).put(y, 1);
}
}else{
Map<Integer,Integer> m = new HashMap<Integer,Integer>();
m.put(y, 1);
map.put(x, m);
}
max=Math.max(max, map.get(x).get(y));
}
result=Math.max(result, max+overlap+1);
}
return result;


}
private int generateGCD(int a,int b){

if (b==0) return a;
else return generateGCD(b,a%b);

}
}

https://discuss.leetcode.com/topic/24011/accepted-java-solution-easy-to-understand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/
public class Solution {
public int maxPoints(Point[] points) {
if(points.length <= 0) return 0;
if(points.length <= 2) return points.length;
int result = 0;
for(int i = 0; i < points.length; i++){
HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
int samex = 1;
int samep = 0;
for(int j = 0; j < points.length; j++){
if(j != i){
if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
samep++;
}
if(points[j].x == points[i].x){
samex++;
continue;
}
double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
if(hm.containsKey(k)){
hm.put(k,hm.get(k) + 1);
}else{
hm.put(k, 2);
}
result = Math.max(result, hm.get(k) + samep);
}
}
result = Math.max(result, samex);
}
return result;
}
}

谢谢你,可爱的朋友。