Time Limit Exceed O(n2)


  • 0
    F

    I used the suggested method to find a,b,c for a line and use it as the key for a HashMap, but still getting the time limit exceed problem with O(n2)

    public static int maxPoints(Point[] points) {
                HashMap<Line, Set<Integer>> pointCount = new HashMap();
                HashMap<Point, Set<Integer>> samePoints = new HashMap();
                int result = 2;
                Point first, second;
                Set<Integer> pointsLine;
                if (points.length < result + 1) {
                    return points.length;
                }
                for (int i = 0; i < points.length; i++) {
                    first = points[i];
                    for (int j = points.length - 1; j > i; j--) {
                        second = points[j];
                        if (first.x == second.x && first.y == second.y) {
                            if (samePoints.containsKey(first)) {
                                pointsLine = samePoints.get(first);
                                pointsLine.add(i);
                                pointsLine.add(j);
                                samePoints.put(first, pointsLine);
                                result = result < pointsLine.size() ? pointsLine.size() : result;
                            } else {
                                pointsLine = new HashSet();
                                pointsLine.add(i);
                                pointsLine.add(j);
                                samePoints.put(first, pointsLine);
                            }
                        } else {
                            Line current = new Line(first, second);
                            if (pointCount.containsKey(current)) {
                                pointsLine = pointCount.get(current);
                                pointsLine.add(i);
                                pointsLine.add(j);
                                pointCount.put(current, pointsLine);
                                result = result < pointsLine.size() ? pointsLine.size() : result;
                            } else {
                                pointsLine = new HashSet();
                                pointsLine.add(i);
                                pointsLine.add(j);
                                pointCount.put(current, pointsLine);
                            }
                        }
                    }
                }
                return result;
            }
    
    class Line {
    
        int a;
        int b;
        int c;
    
        Line() {
            a = 0;
            b = 0;
            c = 0;
        }
    
        Line(Point p1, Point p2) {
            a = p1.y - p2.y;
            b = p1.x - p2.x;
            c = p2.x * p1.y - p1.x * p2.y;
            int gcd = gcd();
            a = a / gcd;
            b = b / gcd;
            c = c / gcd;
        }
    
        @Override
        public boolean equals(Object object) {
            if (object instanceof Line) {
                Line temp = (Line) object;
                return (this.a == temp.a && this.b == temp.b && this.c == temp.c);
            } else {
                return false;
            }
    
        }
        
        @Override
        public int hashCode() {
            return this.a ^ this.b * this.c;
        }
    
        public int gcd() {
            BigInteger int1 = new BigInteger(Integer.toString(a));
            BigInteger int2 = new BigInteger(Integer.toString(b));
            BigInteger int3 = new BigInteger(Integer.toString(c));
            BigInteger gcd0 = int1.gcd(int2);
            BigInteger gcd = gcd0.gcd(int3);
            return gcd.intValue();
        }
    }

  • 1
    P
    public class Solution{
        class Line {
    
            Line(Point p1, Point p2) {
                a = p2.y - p1.y; // use p2.y - p1.y
                b = p1.x - p2.x;
                c = p2.x * p1.y - p1.x * p2.y;
                int gcd = gcd();
                a = a / gcd;
                b = b / gcd;
                c = c / gcd;
                if(a<0 || a==0 && b < 0) { // normalized a to be non-negative or b to be non-negative when a is 0
                    a = -a;
                    b = -b;
                    c = -c;
                }
            }
        }
    }

  • 0
    P

    Could you please explain why is it necessary to normalize a,b,c?


  • 0
    P

    Simply because we have to make sure that there is a one-to-one mapping from lines to (a, b, c)


  • 0
    P

    I might be completely ignorant on this, but I still don't get it. Through any 2 given points won't there always exists exactly one line?


  • 0
    P

    You are right, there would be exactly one line, but there might be more than one representation for each line. e.g. x+2y+3=0 and 2x+4y+6=0 would represent the same line.


  • 0
    P

    Aaaay, so stupid! So we are looking for the gcd of A, B,C and then dividing the equation with it. Thanks porker2008!


  • 0
    B

    Hi fxqw820, could you please explain to me how/why did you design the hashCode() function in this way? Thank you~


Log in to reply
 

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