Algorithm {Max Points on a Line}

Today we will try to solve next problem from leetcode. The problem is Max Points on a Line.

Problem description:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

So, that is short desciption…. Try Stop and Think …

What do we have, we have input array/list of points and should return max number of the points on one line. We can try to remember school math course and one part is Collinear.

Three or more points P1,P2 ,P3 , …, are said to be collinear if they lie on a single straight line .

Hm, this is our case 🙂, we should find max points on the one line. Ok, Lets go to implement it.

    public int maxPoints(Point[] points) {
        if (points == null)
            return 0;
 
        if (points.length <= 1 || isOnePoint(points))
            return points.length;
        int max = 2; // 2 points are collinear
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                    continue;
                int pointsCount = 2;
                for (int k = 0; k < points.length; k++) {
                    if (k != i && k != j && areCollinear(points[i], points[j], points[k])) {
                        pointsCount++;
                    }
                }
                max = Math.max(max, pointsCount);
            }
        }
        return max;
    }
 
    boolean areCollinear(Point a, Point b, Point c){
        return (a.x - b.x) * (c.y-b.y) - (c.x-b.x) * (a.y-b.y) == 0; // collinearity formula (x1 - x2)/(x2 - x3) = (y1 -y2)/(y2 - y3) 
    }
 
    boolean isOnePoint(Point[] x) {
        int x0 = x[0].x;
        int y0 = x[0].y;
        for (int i = 1; i < x.length; i++) {
            if (x[i].x != x0 || x[i].y != y0)
                return false;
        }
        return true;
    }

So, that is easy, with one trick , is checking if all input array contains the same points.

        if (points.length <= 1 || isOnePoint(points))
            return points.length;

Other cases are easy to understand, run 3 loops (to get 3 Points) check if the points different and if collinear (lay on the one line) increase count of the points, after that check with max value, if count > max assign max to current count and try other points.

The complexity of current implementation is O (N^3), memory O (1) 🙁,  but leetcode accepted that solution, so this is good, but…

Can we improve current solution?

Generally yes, we can use some container like Map, for storing lines and count of the Points on that line and after that just choose what line contains max count of Points. My friend solved the problem using that approach, Complexity will be O (N^2) and memory usage O (N).

Thanks.