LeetCode link

Intuition

  • Each two points can lie on one line, use a map to save all the lines, key is the line(no matter the form you save, here is using the string(a_b) to identify the line), value is all the index of the points.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int maxPoints(Point[] points) {
if (points.length == 1) {
return 1;
}
Map<String, Set<Integer>> map = new HashMap<>();
int max = 0;
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
Point p1 = points[i];
Point p2 = points[j];
double a = (p1.y - p2.y) * 1.0 / (p1.x - p2.x);
double b = (p1.x * p2.y - p2.x * p1.y) * 1.0 / (p1.x - p2.x);
String key = a + "_" + b;
map.putIfAbsent(key, new HashSet<Integer>());
Set set = map.get(key);
set.add(i);
set.add(j);
max = Math.max(max, set.size());
}
}
return max;
}
}

problem

WA.

reason

The points may be duplicate.


modification

  • When two points are the same, continue.
  • When meet a new point on a line, add the count of the point to the point-number of the line at once. Mark this point is added of this 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
class Solution {
public int maxPoints(Point[] points) {
if (points.length == 1) {
return 1;
}
Map<String, Set<Integer>> map = new HashMap<>();
Map<String, Integer> counts = new HashMap<>();
Map<String, Integer> maxCounts = new HashMap<>();
for (Point p: points) {
String key = p.x + "_" + p.y;
counts.putIfAbsent(key, 0);
counts.put(key, counts.get(key) + 1);
}
int max = 0;
for (int i = 0; i < points.length - 1; i++) {
for (int j = i + 1; j < points.length; j++) {
Point p1 = points[i];
Point p2 = points[j];
String key = "";
if (p1.x == p2.x && p1.y == p2.y) {
continue;
}
if (p1.x == p2.x) {
key = p1.x + "_";
} else if (p1.y == p2.y) {
key = "_" + p1.y;
} else {
double a = (p1.y - p2.y) * 1.0 / (p1.x - p2.x);
double b = (p1.x * p2.y - p2.x * p1.y) * 1.0 / (p1.x - p2.x);
if (b == 0) {
b = 0;
}
key = a + "_" + b;
}
map.putIfAbsent(key, new HashSet<Integer>());
maxCounts.putIfAbsent(key, 0);
Set set = map.get(key);
int maxCount = maxCounts.get(key);
if (!set.contains(p1.x + "_" + p1.y)) {
maxCount += counts.get(p1.x + "_" + p1.y);
}
if (!set.contains(p2.x + "_" + p2.y)) {
maxCount += counts.get(p2.x + "_" + p2.y);
}
set.add(p1.x + "_" + p1.y);
set.add(p2.x + "_" + p2.y);
max = Math.max(max, maxCount);
maxCounts.put(key, maxCount);
}
}
return max;
}
}

problem

WA.

reason

Miss the situation that all the points are the same.


modification

add the case of all points are the same.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Map<String, Set<Integer>> map = new HashMap<>();
Map<String, Integer> counts = new HashMap<>();
Map<String, Integer> maxCounts = new HashMap<>();
int pointCounts = 0;
for (Point p: points) {
String key = p.x + "_" + p.y;
if (counts.putIfAbsent(key, 0) == null) {
pointCounts++;
}
counts.put(key, counts.get(key) + 1);
}
if (pointCounts <= 1) {
return points.length;
}

problem

WA.

Input:
[[0,0],[94911151,94911150],[94911152,94911151]]
Output:
3
Expected:
2

reason

Big number, the precision is not enough.


modification

Here’s the answer found on the net.I’m still confused by the solution.

  • To get rid of the precision problems, we treat slope as pair ((y2 – y1), (x2 – x1)) instead of ratio and reduce pair by their gcd before inserting into map. In below code points which are vertical or repeated are treated separately.
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
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);
}
}