Sunday, April 6, 2014

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

We first create a map of the points and the number of appearances. Then we traverse the array in a double loop to create all the possible lines keeping them in a HashMap, thus we have to override the equals and hashCode. We also keep the points in each Line instance.
The whole algorithm runs in $O(n^2)$.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) 
    {
        int nPoints = 0;
        //Remove duplicates
        HashMap<Point, Integer> pointMap = new HashMap<Point, Integer>();
        for(int i=0; i<points.length; i++)
        {
            if(!pointMap.containsKey(points[i]))
                pointMap.put(points[i],0);
            pointMap.put(points[i],pointMap.get(points[i])+1);
        }
        HashMap<Line, Line> lines = new HashMap<Line, Line>();
        Point[] points2 = pointMap.keySet().toArray(new Point[0]);
        for(int i=0; i<points2.length-1; i++)
        {
            for(int j=i+1; j<points2.length; j++)
            {
                Line l = new Line(points2[i],points2[j],pointMap.get(points2[i]),pointMap.get(points2[j]));
                if(!lines.containsKey(l))
                    lines.put(l,l);
                else
                {
                    lines.get(l).addPoint(points2[i], pointMap.get(points2[i]));
                    lines.get(l).addPoint(points2[j], pointMap.get(points2[j]));
                }
                nPoints = lines.get(l).getNumberPoints() > nPoints ? lines.get(l).getNumberPoints() : nPoints;
            }
        }
        return nPoints>0 ? nPoints : points.length;
    }
    
    public class Line
    {
        double yo;
        double slope;
        int nPoints=0;
        HashSet<Point> pointsLine;
        
        public Line(Point p1, Point p2, int p1Apearances, int p2Apearances)
        {
            if(p2.x == p1.x)
            {
                slope = Double.POSITIVE_INFINITY;
                yo = p2.x*1.0;
            }
            else
            {
                slope = 1.0*(p1.y-p2.y)/(p1.x-p2.x);
                yo =  p1.y-slope*p1.x;
            }
            pointsLine = new HashSet<Point>();
            addPoint(p1, p1Apearances);
            addPoint(p2, p2Apearances);
        }
        
        public void addPoint(Point p1, int nAppearances)
        {
            if(!pointsLine.contains(p1))
            {
                pointsLine.add(p1);
                nPoints+=nAppearances;
            }
        }
        
        public int getNumberPoints()
        {
            return nPoints;
        }
        
        public boolean equals(Object o)
        {
            if(!(o instanceof Line))
                return false;
            Line otherLine = (Line) o; 
            return otherLine.yo == yo && otherLine.slope == slope;
        }
        
        public int hashCode()
        {
            int hash = 3;
            hash = hash * 7 + Double.valueOf(yo).hashCode();
            hash = hash * 7 + Double.valueOf(slope).hashCode();
            return hash;
        }
    }
}

No comments :

Post a Comment