LeetCode - Max Points on a Line
Problem description
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Example 1:
1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Analysis
Just for every i, find all other points and its slope to find out the max points in a line for this i.
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
59
60
61
62
63
64
65
66
67
/*
* 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;
*/
public class Solution{
public int maxPoints(int[][] 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][0]-points[i][0];
int y=points[j][1]-points[i][1];
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);
}
}
What to improve
- Note that it might have duplicates point, so the overlap part is necessary.