Accepted java O(n^2) solution using HashMap and slope


  • 1
    N

    the idea is to basically calculate the slope between each point for a fixed point, and do this for all points.
    hash table helps count same slopes.
    things to note:

    • Beware of duplicate points
    • In java, 0 has two values for type Double, 0.0 and -0.0, be careful with these
        public class Solution {
            public int maxPoints(Point[] points) {
                if (points.length <= 2) return points.length;
            
                // map slope to count
                HashMap<Double, Integer> hm = new HashMap<Double, Integer>();
                int maxCount = 1;
            
                for (int i = 0; i < points.length; i++) {
                    // hash each slope and count duplicates
                    hm = new HashMap<Double, Integer>();
                    int duplicate = 0;
                    int maxR = 0;
                
                    for (int j = i + 1; j < points.length; j++) {
                        double slope;
                        if (isDupl(points[i], points[j])) {
                            duplicate++;
                            continue;
                        }
                        else slope = slopeFor(points[i], points[j]);
                    
                        if (hm.containsKey(slope)) {
                            int prevCount = hm.get(slope);
                            hm.put(slope, prevCount + 1);
                            maxR = Math.max(maxR, prevCount + 1);
                        }
                        else {
                            hm.put(slope, 1);
                            maxR = Math.max(maxR, 1);
                        }
                    }
                    maxCount = Math.max(maxCount, maxR + duplicate);
                }
                return maxCount + 1;
            }
        
            private boolean isDupl(Point a, Point b) {
                return a.x == b.x && a.y == b.y;
            }
        
            private double slopeFor(Point a, Point b) {
                double dx = a.x - b.x;
                double dy = a.y - b.y;
                if (dx == 0) return Double.POSITIVE_INFINITY;
                else if (dy == 0) return 0;
                return dy / dx;
            }
        }

  • 0
    H

    what if you have two lines with a tiny difference in slope?
    Say this difference is so tiny that double type will not catch it


Log in to reply
 

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