Line Through Points

You are given a set of points plotted on a 2D graph. Write code that returns the maximum number of points the line passes through.

The input array will contain points represented by an array of two integers which are a x-coordinate and a y-coordinate [x, y].

Sample Input

points = [
  [1, 1],
  [2, 2],
  [3, 3],
  [0, 4],
  [-2, 6],
  [4, 0],
  [2, 1],
]

Sample Output

4 // A line passes through points: [-2, -6], [0, 4], [2, 2], [4, 0].

Hints

If two lines have the same slope and share a point, then they’re the same line. To store this information in a hash table, you will need to keep track of the slopes of all lines that pass through certain points.

Loop through every single pair of points, picking a Point 2 (p2) for every Point 1 (p1) in order to form a line. For every pair (p1, p2), Store the slope of a line segment in a hash table, and map it to the number of points on that line. If you ever find two identical slopes for lines that both use the same point p1, you can consider these lines to be one and the same, meaning that points p1, p2a, and p2b are all on the same line; in those cases, update the number of points on the slope in the hash table accordingly. You’ll need to reset the hash table at each change of p1.

Optimal Space & Time Complexity

Time Complexity = O(n^2)

Space Complexity = O(n)

n is the number of points

Solution 1

DEFINE FUNCTION lineThroughPoints(points):
    SET maxNumberOfPointsOnLine TO 1
    FOR idx1, p1 IN enumerate(points):
        SET slopes TO {}
        FOR idx2 IN range(idx1 + 1, len(points)):
            SET p2 TO points[idx2]
            SET rise, run TO getSlopeOfLineBetweenPoints(p1, p2)
            SET slopeKey TO createHashableKeyForRational(rise, run)
            IF slopeKey not IN slopes:
                SET slopes[slopeKey] TO 1
            slopes[slopeKey] += 1
        SET maxNumberOfPointsOnLine TO max(maxNumberOfPointsOnLine, max(slopes.values(), default=0))
    RETURN maxNumberOfPointsOnLine

DEFINE FUNCTION getSlopeOfLineBetweenPoints(p1, p2):
    SET p1x, p1y TO p1
    SET p2x, p2y TO p2
    SET slope TO [1, 0]  # slope of a vertical line
    IF p1x != p2x:  # IF line is not vertical
        SET xDiff TO p1x - p2x
        SET yDiff TO p1y - p2y
        SET gcd TO getGreatestCommonDivisor(abs(xDiff), abs(yDiff))
        SET xDiff TO xDiff // gcd
        SET yDiff TO yDiff // gcd
        IF xDiff < 0:
            xDiff *= -1
            yDiff *= -1
        SET slope TO [yDiff, xDiff]
    RETURN slope

DEFINE FUNCTION createHashableKeyForRational(numerator, denominator):
    RETURN str(numerator) + ":" + str(denominator)

DEFINE FUNCTION getGreatestCommonDivisor(num1, num2):
    SET a TO num1
    SET b TO num2
    WHILE True:
        IF a EQUALS 0:
            RETURN b
        IF b EQUALS 0:
            RETURN a
        SET a, b TO b, a % b