Share my accepted Java code with explanation


  • 5
    S
        /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    import java.util.HashMap;
    public class Solution {
        public int maxPoints(Point[] points) {
            if (points.length <= 2){
                return points.length;
            }
            int result=1;
         
          //A line is defined y=a/bx+c, so (a, b, c) will represent a unique line
         // run through each point and calculate (a, b, c) that defines the lines of itself 
         //with all the the remaining points 
            for (int i=0; i<points.length; i++){
                int max=0, countSame=0;
                HashMap<String, Integer> hm = new HashMap<String, Integer>();
                for (int j=i+1; j<points.length; j++){
                    if (points[i].x == points[j].x && points[i].y == points[j].y){
                        countSame++;       //same points will just add to the result
                    }
                    else{
                        String key = normalize(points[i],points[j]);
                        if(hm.get(key) == null){
                            hm.put(key, 1);
                            if(max ==0){
                                max++;
                            }
                        }
                        else {
                           int count = hm.get(key)+1;
                           hm.put(key, count);
                         
                            if (count > max)
                                max = count;
                        }
                    }
                    
                }
                result = Math.max(result, max+countSame+1);
            }
    
            
            return result;
        }
        
        //ax+by+c=0 or y=a/b x + c
        private String normalize(Point p1, Point p2){
            int a, b;
            float c;
            
            if (p1.x == p2.x){  //a line parallel to y axis
                a = 1;
                b = 0;
                c = -1 * p1.x;
            }
            else if (p1.y == p2.y){ //a line parallel to x axis
                a = 0;
                b = 1;
                c = p1.y;
            }
            else{
                int gcd = gcd(Math.abs(p1.x-p2.x), Math.abs(p1.y-p2.y));
                b = (p2.x-p1.x)/gcd;
                a = (p2.y-p1.y)/gcd;
                if (a*b<0){                   //if the slope<0, always put (-) in front of a 
                    a = -1 * Math.abs(a);
                    b = Math.abs(b); 
                }
                else {
                    a = Math.abs(a);
                    b = Math.abs(b); 
                }
                c = (float)(b*p1.y - a*p1.x)/(float)b;
            }
            return ""+a+"||"+b+"||"+c;     //use this presentation as a key
            
        }
        
        private int gcd(int x, int y) {
            if (y == 0) {
              return x;
            }
            return gcd(y, x % y);
      }
    }

  • 0
    W

    This is indeed a very decent solution and showed my the way to solution. One optimization is you don't have to use <String, Integer> mapping, just <Double, Integer> is enough where Double is the slope of line determined by points[i] and point[j]; then in your normalize() function, you can simply computes the slope.


  • 0
    W
    This post is deleted!

  • 0
    U

    @wenbin4
    This case fails if you use <Double,Integer> instead of <String,Integer>
    [[0,0],[94911151,94911150],[94911152,94911151]]
    The slope of 2 points with origin is 0.9999999894638303 in both the cases.


Log in to reply
 

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