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


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

  • 0
    S

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


  • 1
    A

    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.


  • 1
    E

    There seems a problems with your answer.

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


  • 0
    F

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

  • 0
    E

    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?


  • 0
    C

    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.


  • 0
    C

    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.


Log in to reply
 

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