/**
* 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) {
int maxPts = 0;
for(int i =0; i<points.length; ++i){
Map<String, Integer> maxPtsInLine = new HashMap<String, Integer>();
for(int j=0; j<points.length; ++j){
if(points[i] != points[j]){
int deltaX = points[i].x  points[j].x;
int deltaY = points[i].y  points[j].y;
String key = deltaY == 0 ? "Horizontal" : String.format("%.5f", ((float) deltaX) / deltaY);
if(maxPtsInLine.containsKey(key))
maxPtsInLine.put(key, maxPtsInLine.get(key)+1);
else
maxPtsInLine.put(key, 2);
if(maxPts < maxPtsInLine.get(key))
maxPts = maxPtsInLine.get(key);
}
}
}
return maxPts;
}
}
Why TLE for this solution? Where can I optimize it? Thanks!


Here is a corrected version of your code. I added comments where I changed your code.
public class Solution { // use numOfSamePoints to indicate the number of points that are same to each other int numOfSamePoints = 0; public int maxPoints(Point[] points) { // deal with special cases if (points.length <= 2) { return points.length; } // set initial values to be 2 int maxPts = 2; for(int i = 0; i < points.length; ++i){ // use Double as the key for the HashMap instead of String Map<Double, Integer> maxPtsInLine = new HashMap<Double, Integer>(); //initialize numOfSamePoints numOfSamePoints = 0; for(int j = 0; j < points.length; ++j){ // use i and j instead of points[i] and points[j] for testing if(i != j) { int deltaX = points[i].x  points[j].x; int deltaY = points[i].y  points[j].y; // test if these two points are the same, if so, increase numOfSamePoints by 1 if (deltaX == 0 && deltaY == 0) { numOfSamePoints++; } Double key = deltaY == 0 ? Double.MAX_VALUE : (double)deltaX/deltaY; if(!maxPtsInLine.containsKey(key)) { maxPtsInLine.put(key, 2); } else { maxPtsInLine.put(key, maxPtsInLine.get(key)+1); } } } // only compare the value of the HashMap with maxPts after you have finished putting all keys in the HashMap, instead of // doing that during the process of putting each key for (Double key : maxPtsInLine.keySet()) { if (key != Double.MAX_VALUE) { // if not horizontal, accounts for points that are same to this point maxPtsInLine.put(key, maxPtsInLine.get(key)+numOfSamePoints); } if(maxPts < maxPtsInLine.get(key)) maxPts = maxPtsInLine.get(key); } } return maxPts; } }

i use different point to be a line; then justy another point is in the line or not; its complexity is O(n^3). i optimize it. if (A, B, C, D, E)points is in a line, i cacluate lineAB's points is five, and lineAC, lineAD, line AE, lineBC... are also five.
you must notice that the points may be a point.

i use different point to be a line; then justy another point is in the line or not; its complexity is O(n^3). i optimize it. if (A, B, C, D, E)points is in a line, i cacluate lineAB's points is five, and lineAC, lineAD, line AE, lineBC... are also five.
you must notice that the points may be a point.