# Time Limit Exceed O(n2)

• I used the suggested method to find a,b,c for a line and use it as the key for a HashMap, but still getting the time limit exceed problem with O(n2)

``````public static int maxPoints(Point[] points) {
HashMap<Line, Set<Integer>> pointCount = new HashMap();
HashMap<Point, Set<Integer>> samePoints = new HashMap();
int result = 2;
Point first, second;
Set<Integer> pointsLine;
if (points.length < result + 1) {
return points.length;
}
for (int i = 0; i < points.length; i++) {
first = points[i];
for (int j = points.length - 1; j > i; j--) {
second = points[j];
if (first.x == second.x && first.y == second.y) {
if (samePoints.containsKey(first)) {
pointsLine = samePoints.get(first);
samePoints.put(first, pointsLine);
result = result < pointsLine.size() ? pointsLine.size() : result;
} else {
pointsLine = new HashSet();
samePoints.put(first, pointsLine);
}
} else {
Line current = new Line(first, second);
if (pointCount.containsKey(current)) {
pointsLine = pointCount.get(current);
pointCount.put(current, pointsLine);
result = result < pointsLine.size() ? pointsLine.size() : result;
} else {
pointsLine = new HashSet();
pointCount.put(current, pointsLine);
}
}
}
}
return result;
}

class Line {

int a;
int b;
int c;

Line() {
a = 0;
b = 0;
c = 0;
}

Line(Point p1, Point p2) {
a = p1.y - p2.y;
b = p1.x - p2.x;
c = p2.x * p1.y - p1.x * p2.y;
int gcd = gcd();
a = a / gcd;
b = b / gcd;
c = c / gcd;
}

@Override
public boolean equals(Object object) {
if (object instanceof Line) {
Line temp = (Line) object;
return (this.a == temp.a && this.b == temp.b && this.c == temp.c);
} else {
return false;
}

}

@Override
public int hashCode() {
return this.a ^ this.b * this.c;
}

public int gcd() {
BigInteger int1 = new BigInteger(Integer.toString(a));
BigInteger int2 = new BigInteger(Integer.toString(b));
BigInteger int3 = new BigInteger(Integer.toString(c));
BigInteger gcd0 = int1.gcd(int2);
BigInteger gcd = gcd0.gcd(int3);
return gcd.intValue();
}
}``````

• ``````public class Solution{
class Line {

Line(Point p1, Point p2) {
a = p2.y - p1.y; // use p2.y - p1.y
b = p1.x - p2.x;
c = p2.x * p1.y - p1.x * p2.y;
int gcd = gcd();
a = a / gcd;
b = b / gcd;
c = c / gcd;
if(a<0 || a==0 && b < 0) { // normalized a to be non-negative or b to be non-negative when a is 0
a = -a;
b = -b;
c = -c;
}
}
}
}``````

• Could you please explain why is it necessary to normalize a,b,c?

• Simply because we have to make sure that there is a one-to-one mapping from lines to `(a, b, c)`

• I might be completely ignorant on this, but I still don't get it. Through any 2 given points won't there always exists exactly one line?

• You are right, there would be exactly one line, but there might be more than one representation for each line. e.g. `x+2y+3=0` and `2x+4y+6=0` would represent the same line.

• Aaaay, so stupid! So we are looking for the gcd of A, B,C and then dividing the equation with it. Thanks porker2008!

• Hi fxqw820, could you please explain to me how/why did you design the hashCode() function in this way? Thank you~

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