Programmatically determine the largest number of points that belong to the same straight line

Question

Applying Maths in real-life is fun but can be frustrating when there is a knowledge gap that causes things to not turn out as imagined.

So there is this problem on Leetcode and having applied my knowledge in line geometry, yet I don't understand why my solution failed, I am dying to see the flaw in it!

Problem link: https://leetcode.com/problems/max-points-on-a-line/

My understanding of the problem with determining whether a given point is on a particular line, is by breaking the problem into three scenarios:

1. Vertical line: Just check if x coordinate is same with the line, and if y coordinate is within range.

2. Horizontal line: Just check if y coordinate is same with the line, and if x coordinate is within range.

3. Sloped line: Get the line equation y = mx + b Plug in the point's coordinates into the equation and if they match, the point is in the line!

My program passed 32/35 tests. Calculated output was 16, against the expected output of 18.

Can you help me point out the error without changing the general approach? Having read the official solution, I don't get it why hashmaps would be necessary since we only need to hold the max counter variable and update it when a larger max is obtained.

Below is my solution:

class Solution {
    /**
     * Iterate through all points establishing a line equation, and checking if every other point satisfies it.
     * If given point satisfies the equation, then it is on that line, increment the max counter for that line.
     * Return the max of all max counters for every line.
     *
     * @param points array of int[] containing coordinates (x,y) for each point
     * @return max count of points on the same line
     */
    public int maxPoints(int[][] points) {
        int length = points.length;
        // best case scenario

        if (length <= 2) {
            return length;
        }

        int outerMax = 2;
        for (int i = 0; i < length-1; i++) {
            int x1 = points[i][0];
            int y1 = points[i][1];
            for (int j = i+1; j < length; j++) {
                int innerMax = 2;
                int x2 = points[j][0];
                int y2 = points[j][1];
                if (x1 == x2) {
                    /*
                     * vertical line scenario:
                     * only need to check if other points share the same x coordinate
                     */
                    for (int k = 0; k < length; k++) {
                        if (k == i || k == j) {
                            continue;
                        }
                        int tempX = points[k][0];
                        int tempY = points[k][1];
                        if (tempX == x1) {
                            if ((y1 <= tempY && tempY <= y2) || (y2 <= tempY && tempY <= y1)) {
                                innerMax++;
                            }
                        }
                    }
                } else if (y1 == y2) {
                    /*
                     * horizontal line scenario:
                     * only need to check if other points share the same y coordinate
                     */
                    for (int k = 0; k < length; k++) {
                        if (k == i || k == j) {
                            continue;
                        }
                        int tempX = points[k][0];
                        int tempY = points[k][1];
                        if (tempY == y1) {
                            if ((x1 <= tempX && tempX <= x2) || (x2 <= tempX && tempX <= x1)) {
                                innerMax++;
                            }
                        }
                    }
                } else {
                    /*
                     * sloped line scenario:
                     * get the line equation and put other points to the test
                     */
                    double m = getSlope(x1, x2, y1, y2);
                    double b = getB(m, x1, y1);
                    for (int k = 0; k < length; k++) {
                        if (k == i || k == j) {
                            continue;
                        }
                        int tempX = points[k][0];
                        int tempY = points[k][1];
                        if (isInLine(tempX, tempY, m, b)) {
                            innerMax++;
                        }
                    }
                }
                outerMax = (innerMax > outerMax) ? innerMax : outerMax;
            }
        }
        return outerMax;
    }
    /** apply slope formula: m = (y2-y1)/(x2-x1) */
    double getSlope(int x1, int x2, int y1, int y2) {

        return ((double) y2 - (double) y1) / ((double) x2 - (double) x1);
    }
    /** get the b-value of the line equation */
    double getB(double m, int x, int y) {
        return (double) y - m * x;
    }

    /**
     * compare point(x,y) to current line and determine if point is on the line
     * @param x x-coordinate of target point
     * @param y y-coordinate of target point
     * @param m slope of the line equation
     * @param b b-value of the line equation
     * @return true if point is on the line, false otherwise
     */
    boolean isInLine(int x, int y, double m, double b) {
        return (y == (m * x + b));
    }
}

}

Answer 1

Perhaps you have problems with exact comparison of float values.

Instead use comparison with some precision, where eps is small value like 1.0e-20 (while some test cases might be especially designed to make close but not equal pairs)

boolean isInLine(int x, int y, double m, double b) {
    return (Math.abs(y - (m * x + b)) < eps);
}

Also you can work in rational numbers N/M, where N and M are integers. Note that you can make N and M mutually prime, dividing both by GCD(N,M) - in this case N and M pairs are unique for every line and might be stored in hash map - perhaps you mentioned namely this approach.