Leetcode: 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.

Understand the problem:
the problem gives n points on a 2D plane, find out the maximum number of points that lie on the same line.

Naive Solution:
For every two points i, and j, that form a line, the condition of the third point , say k, lie on the same line is they share the same slope, i.e, 
(p_k.y - p_i.y )      (p_j.y - p_i.y)
-------------------  =  -------------------
(p_k.x - p_i.x)       (p_j.x - p_i.x)

which is equal to:
(p_k.y - p_i.y) * (p_j.x - p_i.x) = (p_j.y - p_i.y) * (p_k.x - p_i.x)

There is one corner case that all points are the same. If in this case, the result is length of the points array. 

Another tricky point to note is that for points (0,0), (1,1) (0,0), the max number of points are expected to be 3, not 2. So in the inner loop, we don't need to check if k resides in the same points as i and j. 

Code (Java):

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        
        if (allPointsAreSame(points)) {
            return points.length;
        }
        
        int max = 0;
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                // If points[i] and points[j] are the same point
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    continue;
                }
                
                int curPoints = 2;
                for (int k = 0; k < points.length; k++) {
                    //if (k != i && k != j && !samePoints(points, k, i) && !samePoints(points, k, j) && sameLine(points, i, k, j)) {
                    if (k != i && k != j && sameLine(points, i, k, j)) {
                        curPoints++;
                    }
                }
                
                max = Math.max(max, curPoints);
             }
        }
        return max;
    }
    
    private boolean allPointsAreSame(Point[] points) {
        for (int i = 1; i < points.length; i++) {
            if (points[0].x != points[i].x || points[0].y != points[i].y) {
                return false;
            }
        }
        return true;
    }
    
    private boolean samePoints(Point[] points, int i, int j) {
        return (points[i].x == points[j].x) && (points[i].y == points[j].y);
    }
    
    private boolean sameLine(Point[] points, int i, int k, int j) {
        Point p_i = points[i];
        Point p_k = points[k];
        Point p_j = points[j];
        
        return (p_k.y - p_i.y) * (p_j.x - p_i.x) == (p_j.y - p_i.y) * (p_k.x - p_i.x);
    }
}

Discussion:
The time complexity of this naive approach is O(n^3), and the space complexity is O(1). 


A better Idea:
A better idea could use a hash map. For any straight line starts from point i to point j, we calculate the slope of the line, and check if the slope is in the map before. If contains, value plus 1; else create the new key, value pair and the value is 1. 

There are two corner cases need to handle:
1. Two points are the same, meaning point j are the same as point i. Use a counter to save the number of same points as the point i.
2. horizontal line: if points[i]. y == points[j].y, so the slope is 0. And we add 0 as the key. 3. vertical line: if points[i].x == points[j].x, so the slope MAX_INTEGER, and add it as the key.

Code (Java):

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        
        int max = 1;
        for (int i = 0; i < points.length - 1; i++) {
            Map<Double, Integer> map = new HashMap<Double, Integer>();
            int samePoints = 0;
            double slope = 0;
            int localMax = 1;
            for (int j = i + 1; j < points.length; j++) {
                // check if point i and j are the same
                if (points[i].x == points[j].x && points[i].y == points[j].y) {
                    samePoints++;
                    continue;
                } else if (points[i].y == points[j].y) {
                    slope = 0.0;
                } else if (points[i].x == points[j].x) {
                    slope = (double) Integer.MAX_VALUE;
                } else {
                    slope = (double) (points[j].y - points[i].y) / (points[j].x - points[i].x);
                }
                
                
                if (map.containsKey(slope)) {
                    map.put(slope, map.get(slope) + 1);
                } else {
                    map.put(slope, 2);
                }
            }
            for (Integer num : map.values()) {
                localMax = Math.max(localMax, num);
            }
            localMax += samePoints;
            max = Math.max(max, localMax);
        }
        return max;
    }
}

 

Discussion:
There are several points need to consider carefully:
1. max, localMax should be initialized as 1. That is because if there is only one point in the input array, the result should be 1, instead of 0.
2. samePoints should be initialized as 0. That is because for the input (0,0), (0,0). 
Since localMax and samePoints then are 1. The result is 2. If samePoints are initialized with 1, then the result would be 3.
3. When we calculate the slope, do remember to cast it as double, else it will be integer / integer, and generate the wrong result. This is really a error prone point.
At last, the time complexity of this approach is O(n^2) and the space complexity is O(n).