Java solution with no double. If you are concerned with using doubles/floats, fear not - there is a way around.


  • 5
    A

    This solution is somewhat slower than the standard solution which uses doubles to store slopes. It, however, guarantees that there will not be any precision error, as long as we are dealing with integers as point coordinates.

    You can read here about the pairing functions that uniquely represent any pair of integers. https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function

    /**
     * We can use a pairing function to represent two integers uniquely.
     * In our case we use a pairing function to represent a fraction, 
     * with first integer being the numerator and second integer being the denominator.
     * Hence, we avoid precision concerns that may come up if we use floats / doubles.
     */
    public int maxPoints(Point[] points) {
        if (points.length < 2) return points.length;
        int max = 2;
        for (Point p1 : points) {
            Map<Integer, Integer> slopes = new HashMap<>(points.length);
            int localMax = 0;
            for (Point p2 : points) {
                int num = p2.y - p1.y;
                int den = p2.x - p1.x;
                
                // pairing functions only work with non-negative integers
                // we store the sign in a separate variable
                int sign = 1;
                if ((num > 0 && den < 0) || (num < 0 && den > 0)) sign = -1;
                num = Math.abs(num);
                den = Math.abs(den);
                
                // pairing functions represent a pair of any two integers uniquely;
                // they can be used as hash functions for any sequence of integers;
                // therefore, a pairing function from 1/2 doesn't equal to that from 3/6
                // even though the slope 1/2 and 3/6 is the same.
                // => we need to convert each fraction to its simplest form, i.e. 3/6 => 1/2
                int gcd = GCD(num, den);
                num = gcd == 0 ? num : num / gcd;
                den = gcd == 0 ? den : den / gcd;
                
                // We can use Cantor pairing function pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2
                // and include the sign
                int m = sign * (num + den) * (num + den + 1) / 2 + den;
                if (slopes.containsKey(m)) slopes.put(m, slopes.get(m)+1);
                else slopes.put(m, 1);
                if (m == 0) continue;
                
                localMax = Math.max(slopes.get(m),localMax);
            }
            max = Math.max(max, localMax + slopes.get(0));
        }
        return max;
    }
    
    public int GCD(int a, int b) {
       if (b == 0) return a;
       return GCD(b,a % b);
    }
    

Log in to reply
 

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