My java accepted solution for your reference (only using array).


  • 14
    K
        public class Solution 
        {
            public int maxPoints(Point[] points) 
            {
                int n=points.length;
                if (n<2) return n;
                int currentL=0,maxL=2,x=0,y=0,dx=0,dy=0,overlap=0,upperB=n;
                for(int i=0; i<upperB; i++)
                {
                    for(int j=i+1; j<n; j++)
                    {
                        currentL=1; 
    /*
     * Given two points: (a,b) and (c,d), the corresponding normal vector is (b-d,c-a)
     * If another point (s,t) is in the same line uniquely defined by (a,b) and (c,d),
     * then (s-a,t-b) dot (b-d,c-a) = 0
     */
                        x=points[i].y-points[j].y;
                        y=points[j].x-points[i].x;
    
    /* If two points are the same, there is no need to check further, 
     * since a line has to be defined by exactly two distinct points.
     */
                        if(x==0 && y==0) 
                            overlap++;
    
    /* Well, it might be the case that duplicates are not consecutive, 
     * but as long as we can have a non-trivial normal vector, it won't matter.
     */ 
                        else 
                        {
                            currentL++;
    
    /*  Explaining (currentL+n-k>maxL):
     *  no further checking is necessary when there isn't enough left to make it surpass maxL. 
     */ 
                            for(int k=j+1; k<n && currentL+n-k>maxL; k++)
                            {
                                dx=points[k].x-points[i].x;
                                dy=points[k].y-points[i].y;
                                if(x*dx+y*dy==0)
                                    currentL++;
                            }
                        }
                        maxL=Math.max(currentL+overlap,maxL);
                    }
    
    /* Explaining (upperB=n-maxL): 
     * it would be crystal clear as soon as you draw a table for combinations of case n>3.
     */
                    upperB=n-maxL;
                    overlap=0;
                }
                return maxL;
            }
        }

  • 0
    H

    superb, clean code and clear explaination


  • 2
    V

    You solution costs time O(n^3). However, the best solution that use map to count slope costs O(n^2 lgn).


  • 0
    K

    Which is true, but I have to say that, since I applied two pruning methods, for the most of cases, it achieves the similar or even better performance than ones using map. Also, mine is more memory efficient.


  • 2
    V
    int maxPoints(vector<Point> &points) 
    {
    	int res=0;
    	for(int i=0;i<points.size();i++){
    		int dup=1;
    		map<double, int> mp;
    		for(int j=i+1;j<points.size();j++){
    			if(points[i].x==points[j].x && points[i].y==points[j].y)
    				dup++;
    			else if(points[i].x==points[j].x)
    				mp[INT_MAX]++;
    			else{
    				double key=double(points[i].y-points[j].y)/double(points[i].x-points[j].x);
    				mp[key]++;
    			}
    		}
    		map<double, int>::iterator iter;
    		int max=0;
    		for(iter=mp.begin();iter!=mp.end();iter++)
    			max=max<iter->second?iter->second:max;
    		max+=dup;
    		res=res<max?max:res;
    	}
    	return res;
    }
    

    Here is my solution. It seems not that accurate in some floating point cases, but it works well on OJ. And it takes 80ms.


  • 0
    K

    I just write it in C++ by only changing .length to .size() and Math.max to max. I achieved 48 ms performance.


  • 0
    K

    You can try it out.


  • 0
    L

    My question is looks like you only take slope of the line as key. How do you handle the case that two lines have same slope but different intercept (intersection on y-axis)?


  • 0
    S

    After each inner loop, he reset the haspmap


  • 0
    S

    The best solution should be O(n^2). Using map to count the slope appearance.


  • 0

    @kecen agreed, and we dont have to worry about Double as the key of hashmap.


Log in to reply
 

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