Sunday, February 9, 2014

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:
How can we know that two points are on the same straight line?---> slope!!!
public class Solution {
    public int maxPoints(Point[] points) {
        // map: slope->count
        HashMap map = new HashMap();

        int max = 0;
        
        // use equation y = k*x + b
        for(int i = 0; i < points.length; i++){
            
            // vertical to x-axis
            int infinite_k = 0;
            int itself = 0;
            for(int j = 0; j < points.length; j++){
                
                int x = points[j].x - points[i].x;
                int y = points[j].y - points[i].y;
                
                // itself
                if(x == 0 && y == 0){
                    itself++;
                }
                else if(x == 0){
                    infinite_k++;
                }
                else{
                    // count the number of points that have same slope(k)
                    float k = (float)y / x;
                    
                    if(map.containsKey(k)){
                        map.put(k, map.get(k)+1);
                    }
                    else{
                        map.put(k, 1);
                    }
                }   
            }
            
            int tmpMax = 0;
            for(int tmp : map.values()){
                tmpMax = Math.max(tmpMax, tmp);
            }
            // plus the number of duplicates for itself
            max = Math.max(max, tmpMax + itself);
            max = Math.max(max, infinite_k + itself);
            map.clear();
        }
        
        return max;
    }
}

No comments:

Post a Comment