Max Points on a Line

How it works

Floating point slopes can introduce precision errors. To avoid this, we represent the slope as a reduced fraction using the GCD of the differences in x and y coordinates. By storing slopes as pairs (or strings) of integers rather than floating point numbers, we eliminate rounding issues. This approach maintains the same algorithmic structure as the previous solution but with more robust comparisons.

Steps

1. If there are 2 or fewer points, return the count directly.
2. For each point i, create a hash map keyed by the normalized slope (using GCD reduction).
3. For every other point j:
   • Compute dx = x_j - x_i and dy = y_j - y_i.
   • Divide both by their GCD to get the canonical slope representation.
   • Increment the count for this slope in the map.
4. Update res with the maximum count plus 1.
5. Return res.

Complexity

• Time complexity: O(n ^ 2 log m)
• Space complexity: O(n)

Where n is the number of points and m is the maximum value in the points.

Things to watch for

Floating Point Precision Errors

Using floating point division to compute slopes introduces precision errors. Two mathematically equal slopes may compare as unequal due to rounding. For example, 1/3 and 2/6 might not be exactly equal as floats. The solution is to represent slopes as reduced fractions using GCD, storing them as pairs or strings of integers.

Handling Vertical Lines

When two points have the same x-coordinate, the slope is undefined (division by zero). Forgetting to handle this case causes runtime errors. Use a special value like infinity or a distinct key (such as "inf" or a tuple like (1, 0)) to represent vertical lines in your slope map.

Negative Zero in Floating Point

In floating point arithmetic, -0.0 and 0.0 are distinct values but should be treated as equal slopes. Horizontal lines going left-to-right and right-to-left produce 0.0 and -0.0 respectively. When using floating point slopes, normalize -0.0 to 0.0 before using it as a hash key.

Inconsistent Slope Normalization with GCD

When using GCD to reduce fractions, ensure consistent sign handling. The GCD of negative numbers can produce inconsistent signs across different implementations. Normalize by always making the denominator positive, or by making the first non-zero component positive. Otherwise, slopes like (-1, 2) and (1, -2) will be treated as different when they represent the same line.

Forgetting to Include the Reference Point

When counting points with the same slope from a reference point, the count only includes other points, not the reference point itself. The total collinear points is count + 1. Forgetting to add one for the reference point will undercount by one for every line.

from typing import List
from collections import defaultdict
from math import gcd

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)

        def gcd(a, b):
            return gcd(b, a % b) if b else a

        res = 1
        for i in range(len(points) - 1):
            count = defaultdict(int)
            for j in range(i + 1, len(points)):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = gcd(dx, dy)
                dx //= g
                dy //= g
                slope = (dx, dy)
                count[slope] += 1
            res = max(res, max(count.values()) + 1)
        return res

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if (points.size() <= 2) {
            return points.size();
        }

        int res = 1;
        for (int i = 0; i < points.size() - 1; i++) {
            unordered_map<string, int> count;
            for (int j = i + 1; j < points.size(); j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                string slope = to_string(dx) + ":" + to_string(dy);
                count[slope]++;
            }
            for (const auto& [slope, freq] : count) {
                res = max(res, freq + 1);
            }
        }
        return res;
    }

private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};