Better way to use HashMap for this question?


  • 1
    I
    import java.util.HashMap;
    public class Solution {
    	public int maxPoints(Point[] points) {
            int size = points.length;
            if(size == 1)
                return 1;
            if(size == 2)
                return 2;
            int maxAll = 0;
            for(int i = 0; i < size - 1; i++){
            	HashMap<Slope,Integer> hm = new HashMap<Slope,Integer>();
                int max = 1;
                int dup = 0;
                for(int j = i + 1; j < size; j++){
                	if(points[j].x == points[i].x && points[j].y == points[i].y){
                		dup++;
                		continue;
                	}
                    Slope s = new Slope(points[j].x-points[i].x,points[j].y-points[i].y);
                    if(hm.containsKey(s)){
                    	int cur = hm.get(s);
                    	hm.put(s, cur+1);
                    	if(cur+1 > max)
                    		max = cur+1;
                    }else{
                    	hm.put(s, 2);
                    	if(max<2)
                    		max = 2;
                    }
                }
                if(max + dup > maxAll)
                	maxAll = max+dup;
            }
            return maxAll;
        }
    	class Slope{
    		public int x;
    		public int y;
    		public Slope(int x,int y){
    			this.x = x;
    			this.y = y;
    		}
    		@Override
    	    public int hashCode() {
    			if(this.x == 0 || this.y == 0)
    				return 1;
    			else{
    				int hash = this.y / this.x;
    				return hash;
    			}
    	    }
    		
    		@Override
    		public boolean equals(Object o){
    			if(o == null)
    				return false;
    			Slope ob = (Slope)o;
    			if(this.x == 0 && ob.x == 0)
    				return true;
    			else if(this.y ==0 && ob.y == 0)
    				return true;
    			else if(this.y * ob.x == this.x * ob.y)
    				return true;
    			else
    				return false;
    				
    		}
    	}
    }
    

    I created a new class named Slope to make it as the key for HashMap entry. It contains attributes x and y as the delta y and delta x used to compute slope of a line. The algorithm is as: For every two points, compute their slope and see if the slope is already in the hashmap. After done with iteration over all possible pairs of points, we then get the max value.

    However, I can't think of an elegant way to use this hashmap approach. I override the hashCode and equals methods in Slope class to make it easy for hashMap's containsKey() operation. But as you can see from my code, the overridden hashCode function is not very well implemented so it would cause quite some collisions.
    I don't know if I'm missing something here. Any better way to use hashmap for this problem?
    BTW, this code's already been accepted.


  • 2
    M

    I used something similar and made a HashMap <Double,Integer> for each point in ascending x order, while storing the vertical slopes as Double.NaN. That allows Double to represent every slope uniquely as (y/x). Since it is already hashable, there's no need to override it. It is a bit unsafe using floating points to make a hash, and -0.0 != 0.0 so you need to adapt there, but it worked out fine and was accepted.


  • 0
    A

    I don't quite understand your solution. How can you just use the slope as the key while a line is defined not only by a slope but also by an offset?


Log in to reply
 

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