True O(n^2) solution (no gcd) and why y = m*x + b is not bad after all


  • 0
    M

    Here is my solution. The idea others had, to use ax + by + c = 0 to store the lines has one big benefit: you can store these three values as integers and therefore can use your Line as key for a Hashmap. But it will also have one downside - you have to take care of cases like 1x + 1y + 0 and 2x+2y + 0 and therefore calculate the gcd which will bump your solution to O(n^2log(n))

    Using the other format y = m*x + b you will end up with fractions which will be float or double which should NEVER be used in Objects that are supposed to be Hashmap keys.

    So how to circumvent this problem? This is the idea: mulitply the slope m and y-distance b (don't know the technical english term) by 1000 and then store this value as int. Basically you're saying you will only need 3 digits after the decimal point with a multiplier by 1000.

    There are two caveats:

    1. We do have limited precision (but 3 digits after the decimal point should be enough here)
    2. If we have "big" points we could get overflow problems (because multiplying by 1000).

    What do you guys think?

    public class Solution {
        public int maxPoints(Point[] points) {
            if(points == null || points.length == 0) { return 0; }
            if(points.length == 1) { return 1; }
            
            Map<Line, Set<Integer>> lineMap = new HashMap<>();
            int max = 2;
            
            for(int i = 0; i < points.length-1; i++) {
                for(int j = i+1; j < points.length; j++) {
                    Line cur = new Line(points[i], points[j]);
                    if(!lineMap.containsKey(cur)) {
                        Set<Integer> pointSet = new HashSet<>();
                        pointSet.add(i);
                        pointSet.add(j);
                        lineMap.put(cur, pointSet);
                    } else {
                        Set<Integer> pointSet = lineMap.get(cur);
                        if(!pointSet.contains(i)) {
                            pointSet.add(i);
                        }
                        if(!pointSet.contains(j)) {
                            pointSet.add(j);
                        }
                        max = Math.max(pointSet.size(), max);
                    }
                }
            }
            
            return max;
        }
        
        private static class Line {
            final static int ACC_MULT = 1000;
            
            // Note: slope and yDist are multiplied by ACC_MULT;
            int slope;
            int yDist;
            int xDist;
            boolean infSlope;
            
            Line(Point p1, Point p2) {
                if(p2.x - p1.x == 0) { 
                    infSlope = true;
                    xDist = p1.x;
                } else {
                    slope = ((p2.y - p1.y) * ACC_MULT) / (p2.x - p1.x);
                    yDist = ((p1.x*p2.y-p2.x*p1.y) * ACC_MULT) / (p1.x-p2.x);
                }
            }
            
            @Override
            public boolean equals(Object o) {
                if (o == this) { return true; }
                if (!(o instanceof Line)) { return false; }
                Line line = (Line) o;
                return line.slope == this.slope &&
                       line.yDist == this.yDist &&
                       line.infSlope == this.infSlope &&
                       line.xDist == this.xDist;
            }
            
            @Override
            public int hashCode() {
                int result = 17;
                result = 31 * result + slope;
                result = 31 * result + yDist;
                result = 31 * result + xDist;
                result = 31 * result + ((infSlope) ? 1 : 0);
                return result;
            }
        }
    }

  • 0

    What do you guys think?

    Two things...

    float or double which should NEVER be used in Objects that are supposed to be Hashmap keys

    You have a float/double phobia :-P

    The typical y = m*x + b implementation of course does suffer from inaccuracies since it calculates further with already rounded values, but I challenge you to find a case where using doubles goes wrong in the approach where each point and its slopes dy/dx to all other points are used (like this or this).

    3 digits after the decimal point should be enough here

    You're wrong.

    Your program tells me that (0, 0), (10000, 10000), (100000001, 100000000), and (99999999, 100000000) are all on the same line. And that was the first thing I tried.


  • 0
    M

    Double and float are just not guaranteed to give you the "correct" results (eg. System.out.println(1586.6 - 708.75);) This can introduce really bad bugs in your code, so I would avoid it.

    Yes of course you will find examples where 3 digits after the decimal points are not enough. You will not get 100% accuracy with double either (ignoring that results even maybe wrong with double). The questions is, is it exact enough. I agree that for this use case 3 digits after the decimal point is probably stretching it. (you could increase 1000 to become more exact but even more risk an int overflow).


  • 0

    Yes, I'm obviously aware that doubles aren't exact, but that just means you can't blindly trust them, not that you can never trust them.

    The challenge remains open to break the dy/dx solutions. Can you? Or just find ints a, b, c and d so that

    ((double) a) / b == ((double) c) / d
    

    misjudges those two slopes, i.e., that it returns something different than

    ((long) a) * d == ((long) c) * b
    

    Here's a fun program:

    class Main {
        public static void main(String[] args) {
            long double_wrong = 0, int_wrong = 0;
            int ACC_MULT = 1000;
            for (int a=1; a<=1000000; a+=12345) {
                for (int b=1; b<=1000000; b+=9876) {
                    for (int c=1; c<=1000000; c+=13579) {
                        for (int d=1; d<=1000000; d+=9764) {
                            boolean real_eq = ((long) a) * d == ((long) c) * b;
                            boolean double_eq = ((double) a) / b == ((double) c) / d;
                            boolean int_eq = a * ACC_MULT / b == c * ACC_MULT / d;
                            if (double_eq != real_eq)
                                double_wrong++;
                            if (int_eq != real_eq)
                                int_wrong++;
                        }
                    }
                }
            }
            System.out.println("double was wrong " + double_wrong + " times");
            System.out.println("int was wrong " + int_wrong + " times");
        }
    }
    

    That compares your int method and the straight-forward double division against the correct judgement. The output:

    double was wrong 0 times
    int was wrong 29894 times
    

    Can you adapt your int method so that you get zero wrong times as well? And can you find test cases where the double method fails?


  • 0
    M
    1. Like previously stated it's obvious and does not need any proof that 3 digits after the decimal point is not very accurate.

    2. It is interesting that double did not fail for your loops. Maybe it is a non issue here. Generally it's a mistake to trust floating points numbers as hash keys though still. At some point you may have a horrible bug that only shows up like 0.001% of the time. Because it worked for everything before people will start trusting your method and maybe even don't know your implementation. If you are in a Coding Interview I would at least address this to the interviewer.


Log in to reply
 

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