Max Points on a Line

• If the number of points n is less than or equal to 2, return n.
• Initialize a variable maxCount to 0.
• Iterate through all pairs of points (i, j) to define a line.
• For each line defined by points[i] and points[j], initialize a currentCount to 0.
• Iterate through all points k from 0 to n-1.
• Check if point k is collinear with points i and j using the cross-multiplication formula.
• If point k lies on the line, increment currentCount.
• After checking all points k, update maxCount = max(maxCount, currentCount).
• Return maxCount after all pairs (i, j) have been checked.

The fundamental idea is that three points (x1, y1), (x2, y2), and (x3, y3) are collinear if the slope between (x1, y1) and (x2, y2) is the same as the slope between (x1, y1) and (x3, y3). To avoid division by zero for vertical lines and floating-point precision errors, we use the cross-multiplication form of the slope equality check: (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1).

The algorithm iterates through every pair of points (i, j) to define a line. For each such line, it then performs a full scan of all points k in the dataset to count how many lie on this specific line. The maximum count found throughout this process is the result. Using long for the intermediate products in the cross-multiplication is a safeguard against potential integer overflow, although for the given constraints, int might suffice.

Here is the Java implementation:

1class Solution {2    public int maxPoints(int[][] points) {3        int n = points.length;4        if (n <= 2) {5            return n;6        }7        int maxCount = 0;8        for (int i = 0; i < n; i++) {9            for (int j = i + 1; j < n; j++) {10                int currentCount = 0;11                // Define a line with points i and j, and count all points on it12                for (int k = 0; k < n; k++) {13                    long x1 = points[i][0], y1 = points[i][1];14                    long x2 = points[j][0], y2 = points[j][1];15                    long x3 = points[k][0], y3 = points[k][1];16                    // Check if point k is collinear with i and j17                    if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)) {18                        currentCount++;19                    }20                }21                maxCount = Math.max(maxCount, currentCount);22            }23        }24        return maxCount;25    }26}

• Let n be the number of points. If n <= 2, return n.
• Initialize maxPoints = 1.
• Iterate through each point p_i from i = 0 to n-1, using it as an anchor point.
• For each anchor p_i, create a HashMap<String, Integer> to store counts of points per slope.
• Iterate through every other point p_j from j = i + 1 to n-1.
• Calculate the slope between p_i and p_j. To handle slopes accurately:
  • Represent vertical lines (where dx = 0) with a special string like "inf".
  • For other slopes, calculate dy and dx, find their Greatest Common Divisor (GCD), and use the reduced fraction (dy/gcd) + "/" + (dx/gcd) as the key.
• Increment the count for the corresponding slope in the hash map.
• After iterating through all j for a fixed i, find the maximum count (localMax) in the hash map.
• The total points on the best line through p_i is localMax + 1 (including p_i). Update the global maxPoints with this value if it's larger.
• After iterating through all anchors i, return maxPoints.

This approach improves the time complexity to O(N^2) by avoiding the third nested loop. The core idea is that all points that are collinear with a given anchor point p_i will have the same slope with respect to p_i.

We iterate through each point p_i and fix it as an anchor. Then, for this p_i, we iterate through all subsequent points p_j (j > i). For each pair (p_i, p_j), we calculate the slope. A crucial part of this approach is how we represent the slope to use it as a key in a hash map. Using floating-point numbers (double) for slopes is unreliable due to precision issues. A robust method is to represent the slope as a simplified fraction dy/dx. We compute dy = y_j - y_i and dx = x_j - x_i, find their Greatest Common Divisor (GCD), and use the string "(dy/gcd)/(dx/gcd)" as the map key. Vertical lines, where dx = 0, are a special case and can be represented by a constant string like "infinity".

The hash map stores the number of points found for each unique slope relative to the anchor p_i. After checking all other points against p_i, the maximum value in the map gives the maximum number of other points on a single line through p_i. We add 1 to this count (for p_i itself) and update our global maximum. By repeating this for every possible anchor point, we guarantee finding the overall maximum.

Here is the Java implementation:

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxPoints(int[][] points) {6        int n = points.length;7        if (n <= 2) {8            return n;9        }10        int maxPoints = 1;11 12        for (int i = 0; i < n; i++) {13            Map<String, Integer> slopeMap = new HashMap<>();14            for (int j = i + 1; j < n; j++) {15                int dy = points[j][1] - points[i][1];16                int dx = points[j][0] - points[i][0];17                18                String slope;19                if (dx == 0) {20                    // Vertical line21                    slope = "inf";22                } else {23                    int commonDivisor = gcd(dy, dx);24                    slope = (dy / commonDivisor) + "/" + (dx / commonDivisor);25                }26                27                slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);28            }29            30            int currentMax = 0;31            for (int count : slopeMap.values()) {32                currentMax = Math.max(currentMax, count);33            }34            // Add the anchor point itself35            maxPoints = Math.max(maxPoints, currentMax + 1);36        }37        return maxPoints;38    }39 40    // Helper function to compute GCD using Euclidean algorithm41    private int gcd(int a, int b) {42        while (b != 0) {43            int temp = b;44            b = a % b;45            a = temp;46        }47        return a;48    }49}