136. Max Points on a Line

Fix each point as an anchor and count how many other points share the same slope relative to it. Points on one line through the anchor all have equal slope, so the largest slope bucket (plus the anchor itself) gives the best line through that anchor.

Idea

A line is determined by an anchor point and a slope. Fix each point i as the anchor; every other point j defines a slope (dy, dx). All points collinear with i share the same slope, so counting slopes in a hash map and taking the largest bucket (plus 1 for the anchor) gives the most points on a line through i. The overall answer is the best over all anchors.

To compare slopes exactly (no floating point), reduce (dx, dy) by their gcd and normalize the sign so, e.g., (1,2) and (-1,-2) map to the same key.

Algorithm

1. If n <= 2, return n.
2. For each anchor i, build a slope→count map over all j != i; reduce each (dx, dy) by gcd and normalize sign. Track the max bucket + 1.
3. Return the global best.

Worked example: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

The line through (1,1),(3,2),(5,3) (slope 1/2) holds 3 points... and the best line here contains 4 points.

Complexity

• Time: O(n²).
• Space: O(n) per anchor.

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

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int best = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopes = new HashMap<>();
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = gcd(Math.abs(dx), Math.abs(dy));
                if (g != 0) {
                    dx /= g;
                    dy /= g;
                }
                if (dx < 0 || (dx == 0 && dy < 0)) {
                    dx = -dx;
                    dy = -dy;
                }
                String key = dx + "," + dy;
                int c = slopes.getOrDefault(key, 0) + 1;
                slopes.put(key, c);
                best = Math.max(best, c + 1);
            }
        }
        return best;
    }

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