A java solution with notes


  • 113
    R
      /*
         *  A line is determined by two factors,say y=ax+b
         *  
         *  If two points(x1,y1) (x2,y2) are on the same line(Of course). 
    
         *  Consider the gap between two points.
    
         *  We have (y2-y1)=a(x2-x1),a=(y2-y1)/(x2-x1) a is a rational, b is canceled since b is a constant
    
         *  If a third point (x3,y3) are on the same line. So we must have y3=ax3+b
    
         *  Thus,(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
    
         *  Since a is a rational, there exists y0 and x0, y0/x0=(y3-y1)/(x3-x1)=(y2-y1)/(x2-x1)=a
    
         *  So we can use y0&x0 to track a line;
         */
        
        public class Solution{
            public int maxPoints(Point[] points) {
            	if (points==null) return 0;
            	if (points.length<=2) return points.length;
            	
            	Map<Integer,Map<Integer,Integer>> map = new HashMap<Integer,Map<Integer,Integer>>();
            	int result=0;
            	for (int i=0;i<points.length;i++){ 
            		map.clear();
            		int overlap=0,max=0;
            		for (int j=i+1;j<points.length;j++){
            			int x=points[j].x-points[i].x;
            			int y=points[j].y-points[i].y;
            			if (x==0&&y==0){
            				overlap++;
            				continue;
            			}
            			int gcd=generateGCD(x,y);
            			if (gcd!=0){
            				x/=gcd;
            				y/=gcd;
            			}
            			
            			if (map.containsKey(x)){
            				if (map.get(x).containsKey(y)){
            					map.get(x).put(y, map.get(x).get(y)+1);
            				}else{
            					map.get(x).put(y, 1);
            				}   					
            			}else{
            				Map<Integer,Integer> m = new HashMap<Integer,Integer>();
            				m.put(y, 1);
            				map.put(x, m);
            			}
            			max=Math.max(max, map.get(x).get(y));
            		}
            		result=Math.max(result, max+overlap+1);
            	}
            	return result;
            	
            	
            }
            private int generateGCD(int a,int b){
        
            	if (b==0) return a;
            	else return generateGCD(b,a%b);
            	
            }
        }

  • 0
    G
    This post is deleted!

  • 0
    G

    What is your run time?


  • 2
    R

    It has to be O(n^2).


  • 0
    G

    Sorry I mean what was your reported time like how many milliseconds?


  • 0
    R

    496ms Only one run


  • 0
    G

    I sorted the points first, mark the replicates, and then do the calculation on only the unique ones. It runs a little faster (396ms). So it looks like sorting helped a little.


  • 0
    R

    Sorting on one dimension ?


  • 0
    G

    yes. Sorting in one dimension then test Y to remove get those duplicates faster. I suppose we can also sort in Y dimension for all same X points if there are tons of duplicates


  • 0
    R

    Sorting on Two dimensions seems to increase the worst time complexity to O(n^3) if I deduced correctly.


  • 0
    G

    Hmmm, I was wrong. I didn't sort on X or Y. I used a HashMap to group replicated points first O(n), then do the O(N^2) searching.


  • 4
    R

    One c++ solution with the same idea.

    class Solution{
    public:
    	int maxPoints(vector<Point> &points){
    		if (points.size()<=2) return points.size();
    
    		map<int,map<int,int> > map;
    		int result=0;
    
    		for (unsigned int i=0;i<points.size();i++){
    			map.clear();
    			int localmax=0,overlap=0;
    			for (unsigned int j=i+1;j<points.size();j++){
    				int x=points[j].x-points[i].x;
    				int y=points[j].y-points[i].y;
    				//check overlap
    				if (x==0&&y==0){
    					overlap++;
    					continue;
    				}
    				int gcd=generateGCD(x,y);
    				if (gcd!=0){
    					x/=gcd;
    					y/=gcd;
    				}
    				//find x,then y;
    				int curr=++map[x][y];
    				localmax=max(curr,localmax);
    			}
    			result=max(result,localmax+overlap+1);
    		}
    		return result;
    	}
    private:
    	int generateGCD(int a, int b){
    		if (b==0) return a;
    
    		return generateGCD(b,a%b);
    	}
    };

  • 0
    T

    Does your code handle two parallel lines?The two lines have the same x0&&y0, but their points are not on the same line. Thanks.


  • 0
    R

    Yes. Two points at two parrallel lines form a new line.


  • 0
    S

    Thank you for your solution. I have a question: What function did the following code serve?

    if (gcd != 0)
    {
    x /= gcd;
    y /= gcd;
    }


  • 0
    R

    To obtain the smallest integer pairs--->Or to obtain the value the a rational number


  • 0
    K

    I think it will not work in below case. If points lie on two different parallel lines, it will consider as all points lie on same line.
    Suppose consider points (2,4), (2,6), (4,4), (4,6).
    We know that (2,4) and (2,6) lie on line X =2
    and (4,4), (4,6) lies on line X = 4

    for (2,4) and (2,6)
    from your method x = 2-2, y = 6-4, gcd(2,0) == 2

    for (4,4) and (4,6)
    from your method x = 4-4, y = 6-4 gcd(2, 0) == 2

    All 4 points will end up getting stored in same location although those are on 2 different paraller lines


  • 1
    R

    It works very well. Please check your case with my code again with special caution at "@code {map. clear();} @Line 9". You should be able to figure out.


  • 2
    D

    I think check
    if (gcd!=0)
    is redundant because the only possibility is x==0&&y==0, which is already handled before.


  • 0
    R

    You are right


Log in to reply
 

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