# Why TLE for this solution? Where can I optimize it? Thanks!

• ``````/**
* 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;
}
}``````

• Could you please update your post with some algorithm explanation, also some comments in code? Thanks.

• For every two points, only need to calculate slope once, however, your solution calculates twice: (point_1, point_2), (point_2, point_1), which is not necessary.

(float) deltaX) / deltaY can not determine whether they are on the same line. Two lines can have the same slop but parallel.

``````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;
}
}
``````

• but the outer loop already determined points[i], so every other point that has the same slope with points[i] will be on the same line right?

• 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.

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