Java solution with Map (19 ms, beats 95%)


  • 0
    Z

    Use slope as the map key. Since the slope is type Double, slope = 0 will not be precise. So this case we have to count separately. My prune at the first for loop might be the reason why this code is a little faster.

        public int maxPoints(Point[] points) { 
            if (points == null || points.length == 0) return 0;
            int res = 0;
            for (int i = 0; i < points.length - res; i++) {
                // if the total points left is less than the updated res, we don't need to continue.
                HashMap<Double, Integer> slopes = new HashMap<Double, Integer>();
                int vertCount = 1, horiCount = 1, repeat = 0, currMax = 0;
                for (int j = i + 1; j < points.length; j++) {
                    if (points[j].x == points[i].x && points[j].y == points[i].y) {
                        repeat++;
                    } else if (points[j].x == points[i].x && points[j].y != points[i].y) {
                        vertCount++;
                    } else if (points[j].x != points[i].x && points[j].y == points[i].y){
                        horiCount++;
                    } else {
                        double slope = ((double)(points[j].y - points[i].y)) / (points[j].x - points[i].x);
                        int count = slopes.containsKey(slope) ? slopes.get(slope) + 1 : 2;
                        currMax = Math.max(currMax, count);
                        slopes.put(slope, count);                    
                    }
                }
                res = Math.max(res, Math.max(currMax, Math.max(vertCount, horiCount)) + repeat);
                // repeated points should be added to all the cases
            }
            return res;        
        }
    

Log in to reply
 

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