Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3]] Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Approach: Fixed Anchor with Normalized Slopes

Algorithm

1. For each point as the anchor, consider every other point and compute the slope of the line through them
2. Reduce each slope to a canonical form by dividing dy and dx by their greatest common divisor, so 6/4 and 3/2 become the same key
3. Count how many other points share each normalized slope with the anchor; the maximum count plus the anchor itself is the longest line through that anchor
4. Track duplicate points with the anchor separately (not present here since all points are unique, but harmless to guard)
5. Take the global maximum over all anchors; with fewer than 3 points the answer is the point count

Time & Space Complexity

• Time Complexity: O(n²) - for each of n anchors, all other points are scanned
• Space Complexity: O(n) - the slope-count map for one anchor at a time

Java Implementation

import java.util.HashMap;
import java.util.Map;

public class MaxPointsOnALine {

    public static int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }

        int max = 0;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeCount = new HashMap<>();
            int duplicate = 0;
            int localMax = 0;

            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                if (dx == 0 && dy == 0) {
                    duplicate++;
                    continue;
                }

                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                String key = dx + "," + dy;

                int count = slopeCount.getOrDefault(key, 0) + 1;
                slopeCount.put(key, count);
                localMax = Math.max(localMax, count);
            }

            max = Math.max(max, localMax + duplicate + 1);
        }
        return max;
    }

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

    // Test method
    public static void main(String[] args) {
        int[][] points1 = {{1, 1}, {2, 2}, {3, 3}};
        System.out.println("maxPoints([[1,1],[2,2],[3,3]]): " + maxPoints(points1)); // Expected: 3

        int[][] points2 = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
        System.out.println("maxPoints([[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]): "
                + maxPoints(points2)); // Expected: 4
    }
}

Example Walkthrough

For points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]:

1. Anchor [1,1]: slopes to [3,2], [5,3] reduce to 1/2 (2 points), so this line has 3 points
2. Anchor [4,1]: slopes to [3,2], [2,3], [1,4] all reduce to -1/1 (3 points), so this line has 4 points: [4,1],[3,2],[2,3],[1,4]
3. No anchor yields more than 4; the answer is 4

Key Points

1. Slope Canonicalization: Reducing by gcd makes proportional slopes (e.g. 2/4 vs 1/2) collapse to one key
2. Floating-Point Free: Integer pairs are exact, avoiding precision errors from double slopes
3. Sign Handling: gcd on absolute values plus keeping the reduced sign makes -1/2 and 1/-2 identical
4. Anchor + Duplicates: The result for an anchor is the top slope count plus duplicates plus the anchor itself
5. O(n²): With n <= 300, the quadratic scan is comfortably fast