Accepted Java Solution, easy to implement with some explanation


  • 0
    S
    /* The implementation is based on the idea http://www.geeksforgeeks.org/count-maximum-points-on-same-line/. */
    public class Solution {
        
        public int maxPoints(Point[] points) {
            if (points.length <= 2) return points.length;
            
            HashMap<Slope, Integer> map = new HashMap<Slope, Integer>();
            int max = 0;
            
            for (int i = 0; i < points.length; i++) {
                int duplicate = 0;
                int vertical = 0;
                int m = 0;
                for (int j = i + 1; j < points.length; j++) {
                    int x = points[i].x - points[j].x;
                    int y = points[i].y - points[j].y;
                    if (x == 0 && y == 0) {
                        duplicate++;
                    } else if (x == 0) {
                        vertical++;
                    } else {
                        int d = gcd(x, y);
                        Slope slope = new Slope(x / d, y / d);
                        Integer c = map.get(slope);
                        if (c == null) {
                            map.put(slope, 1);
                        } else {
                            map.put(slope, c + 1);
                        }
                        m = Math.max(m, map.get(slope));            
                    }
                    m = Math.max(m, vertical);
                }
                max = Math.max(max, m + duplicate + 1);
                map.clear();
            }
            return max;
        }
        
        public int gcd(int a, int b) {
            return (b == 0) ? a : gcd(b, a % b);
        }
    
    
        class Slope {
            int x;
            int y;
            Slope(int x, int y) {
                this.x = x;
                this.y = y;
            }
            @Override 
            public int hashCode() {
                // deal with sign e.g. when y1/x1 == y2/x2, but '-' sign happens on y1 and x2.
                if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
                    return (x * 31) ^ y;
                } else {
                    return -((Math.abs(x) * 31) ^ (Math.abs(y)));
                }
            }
            @Override 
            public boolean equals(Object o) {
                if (o instanceof Slope) {
                    Slope obj = (Slope) o;
                    return (hashCode() == obj.hashCode());
                }
                return false;
            }
        }
        
    }
    

Log in to reply
 

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