Accepted Java solution, easy to understand.


  • 70
    B
        /**
     * 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) {
            if(points.length <= 0) return 0;
            if(points.length <= 2) return points.length;
            int result = 0;
            for(int i = 0; i < points.length; i++){
                HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
                int samex = 1;
                int samep = 0;
                for(int j = 0; j < points.length; j++){
                    if(j != i){
                        if((points[j].x == points[i].x) && (points[j].y == points[i].y)){
                            samep++;
                        }
                        if(points[j].x == points[i].x){
                            samex++;
                            continue;
                        }
                        double k = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                        if(hm.containsKey(k)){
                            hm.put(k,hm.get(k) + 1);
                        }else{
                            hm.put(k, 2);
                        }
                        result = Math.max(result, hm.get(k) + samep);
                    }
                }
                result = Math.max(result, samex);
            }
            return result;
        }
    }

  • 1
    S

    I love this solution, easy to understand


  • 0
    J

    This solution is quite nice


  • 0
    Y
    This post is deleted!

  • 0
    K

    Is it possible to use Double as key in HashMap?


  • 0
    W

    some help needed, where did I miss, following your logic, trys to do some optimization

    public class Solution {
        public int maxPoints(Point[] points) {
        // Write your code here
        if (points == null || points.length == 0){
            return 0;
        }
        if (points.length < 2) 
            return points.length;
        
        int res = -1;
        for (int i = 0; i < points.length; i++){
            int samex = 1;
            int samep = 0;
            HashMap<Double, Integer> count = new HashMap<Double, Integer>();
            for (int j = i + 1; j < points.length; j++){
               if (points[j].x == points[i].x && points[j].y == points[i].y){
                   samep++;
                }
                if (points[j].x == points[i].x){
                    samex ++;
                    continue;
                }
                double slope = (double)(points[j].y - points[i].y) / (double) (points[j].x - points[i].x);
                if (count.containsKey(slope)){
                    count.put(slope, count.get(slope) + 1);
                } else {
                    count.put(slope, 2);
                }
                res = Math.max(res, count.get(slope) + samep); 
            }
            res = Math.max(res, samex);
        }
        return res;
    }
    

    }


  • 6
    B

    Is this hashing just using the slope? How does it take into account parallel lines?


  • 0
    Y
    This post is deleted!

  • 0
    H

    I think this is the easiest solution to understand!!!! Thanks!!^^


  • 1
    Y

    right, I was thinking about the question: what if there are multiple parallel lines? Do you have any answer to it now?


  • 6
    V

    @bitvector & &yjiang01
    The above code takes care of parallel lines, since it is considering lines passing through one point at a time.

    Lines having the same slope and passing through one point are the same line.


  • 1
    V

    It might be okay to start j from i+1, since you've already counted all lines before that.


  • 0
    L

    Quite nice, but wrong, example: [[0,0],[1,1],[0,0]] .samep is limited by the i-index


  • 4
    W

    Using double as a key is a bad idea


  • 0
    A
    This post is deleted!

  • 0
    Y

    I tried to change the j start from i+1 and got a wrong result. Can anyone explain why?


  • 0
    W
    This post is deleted!

  • 0

    @weimamarvin It's not a problem. Yes, if a point has points both on its left and its right, then they'll get counted separately. But since the solution tries every point as the center, it'll also try the leftmost and the rightmost of all those points as the center, and then the separate counting doesn't matter because one side will be empty.


  • 0
    W
    This post is deleted!

  • 0

    @weimamarvin said in Accepted Java solution, easy to understand.:

    @StefanPochmann
    if we add the sentence if(k==0.0) k=0.0 after the computing slope sentence. Actually, I tried it and it failed.

    I just tried that and it worked. As I had expected. What exactly did you do? Probably better show the whole code.


Log in to reply
 

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