O(kn^2) solution from CCI 150 where k is the avg # of point pairs lying on same line; any improvement?


  • 0
    M

    This algorithm is provided in the book Cracking the Coding Interview,5th edition, Problem 7.6. For each pair of points, generate a Line object and store it in a hash table, and track the line that has largest number of duplicate lines in the hash table, which is also the line that passes largest number of lines. Double values are not precise regarding identity; thus there some functions to correct it.

    k is the average number of point pairs lying on same line. For example if there are 4 points all lying on same line, as 4 points can construct 6 lines (there are 6 pairs of points, each pair can represent 1 line), k is 6.

    import java.util.*;
    
    public static class Line {// nested class Line
    	Double slope; //slope of the line, null if the line is vertical to x-axis
    	Double xInt; //x-intercept, y-intercept if the line is vertical to y-axis
    	Line(){slope=null;xInt=null;}
    	Line(Double slope, Double xInt){this.slope=slope;this.xInt=xInt;}
    	Line(Point a, Point b){//Line construct function given two points
    		int deltaX = a.x-b.x;
    		int deltaY = a.y-b.y;
    		if (deltaX==0){
    			this.slope=null;
    			this.xInt=Double.valueOf(a.x);
    		}else if (deltaY==0){
    			this.slope=0.0;
    			this.xInt = Double.valueOf(a.y);
    		}else{
    			this.slope = (double)deltaY/(double)deltaX;
    			this.xInt = a.x-a.y/this.slope;
    		}
    	}
    	public boolean nearlyEquals(Double a, Double b){
    		return (a==null && b==null)||(Math.abs(a-b)<.0001);
    	}
    	
    	public boolean nearlyEquals(Object o){is same line? true=same; false=not same
    		if (o==null) return false;
    		if (!(o instanceof Line)) return false;
    		Line to = (Line) o;
    		return nearlyEquals(this.slope, to.slope) && nearlyEquals(this.xInt, to.xInt);
    	}
    	public Double getNearSlope(){// get quantized double value of slope from a double value of slope to remove difference between double values. This is not always necessary.
    		if(this.slope==null) return null;
    		return ((int)(this.slope/.0001))*0.0001;
    	}
    	public boolean passesPoint(Point p){// does the Line pass the Point? true = pass; false = not pass
    		if (p==null) return false;
    		if(this.slope==null){
    			return nearlyEquals(Double.valueOf(p.x), this.xInt);
    		}
    		if (this.slope==0){
    			return nearlyEquals(this.xInt, Double.valueOf(p.y));
    		}
    		return nearlyEquals(Double.valueOf(p.x), 1/this.slope*p.y+xInt);
    	}
    }
    public static int count(Hashtable<Double, ArrayList<Line>> lines, Line line){// count the number of lines in *lines* that are same as *line*. The more duplicates the line has in lines, the more points it passes.
    	ArrayList<Line> linesList = lines.get(line.getNearSlope());
    	int count=0;
    	for (Line oneLine : linesList){
    		if (line.nearlyEquals(oneLine)) count++;
    	}
    	return count;
    }
    public static int count(ArrayList<Line> nullLinesList, Line line){// count the number of lines in * nullLinesList* that are same as *line*. *nullLinesList* is the list of lines that have null value of slopes. The more duplicates the line has in lines, the more points it passes.
    	int count=0;
    	for (Line oneLine : nullLinesList){
    		if (line.nearlyEquals(oneLine)) count++;
    	}
    	return count;
    }
    public static int maxPoints(Point[] points){
    	if (points==null || points.length<=0) return 0;
    	if(points.length==1) return 1; 
    	Hashtable<Double, ArrayList<Line>> lines = new Hashtable<Double, ArrayList<Line>>();
    	int max = 0;
    	Line optimalLine = null;
    	ArrayList<Line> nullLinesList = new ArrayList<Line>();
    	for (int i=0;i<points.length-1;++i){//count 
    		for (int j=i+1;j<points.length;++j){
    			Line line = new Line(points[i], points[j]);
    			ArrayList<Line> linesList = null;
    			Double key = line.getNearSlope();
    			int num;
    			if (key==null){
    				nullLinesList.add(line);	
    				num = count(nullLinesList, line);
    			}else{
    				if (lines.containsKey(key)){
    					linesList = lines.get(line.getNearSlope());
    				}else{
    					linesList=new ArrayList<Line>();
    					lines.put(key, linesList);
    				}
    				linesList.add(line);
    				num = count(lines, line);					
    			}
    			if (max < num){
    				max = num;
    				optimalLine = line;
    			}
    		}
    	}
    	if (optimalLine==null) return 0;
    	max = 0;
    	for (int i=0;i<points.length;++i){
    		if(optimalLine.passesPoint(points[i]))max++;
    	}
    	return max;
    }

  • 0
    S

    Hi MitchellHe, could you please update your post with algorithm details? Not everyone knows what 'O(kn^2) solution from CCI 150' is. Also, your code is too long, please add comments in it, people is hard to understand it and give you any hints. Thanks.


Log in to reply
 

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