Max Points on a Line [Hard] — Slope Hashing with GCD [Google / Amazon]

Problem Statement#

Given an array points where points[i] = [xi, yi] represents a point on a 2D 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
• -10^4 <= xi, yi <= 10^4
• All points are unique (per the updated constraint on LeetCode)

Why This Problem Matters#

This is one of those problems where the core challenge is not the algorithm — it is recognizing the data representation trap. Your first instinct will be to compute slope as a float (dy / dx) and store it in a HashMap. That instinct will fail you silently. Two points that are mathematically collinear with a third may produce slopes like 0.3333333333333333 and 0.33333333333333337 due to floating-point rounding, causing them to hash to different buckets. Your answer will be off by one or two, and the bug will be invisible.

LeetCode 149 is a Google and Amazon staple at the Hard level because it tests whether you understand the difference between mathematical equality and floating-point equality — a distinction that matters deeply in production systems. The correct fix (reducing slope to a canonical integer fraction using GCD) is elegant, and knowing it cold is a differentiator.

Beyond the interview circuit, the underlying pattern — grouping objects by a normalized key derived from a computed relationship — appears in clustering, duplicate detection, and geometric algorithms used in graphics, mapping, and computational geometry. This is not a throwaway puzzle.

The Slope Hashing Insight#

Why Not Use Float Division?#

Two slopes are equal if and only if they represent the same rational number. When you compute dy / dx as a float, you introduce rounding. Consider the slope between (0, 0) and (1, 3): dy/dx = 3.0. Now consider the slope between (0, 0) and (100000, 300001): dy/dx is approximately 3.00001 — not exactly 3.0. If these three points were actually collinear, a float-based HashMap would not group them together correctly.

The fix is to represent slope as a reduced fraction using integer arithmetic. Instead of 3.0, store the pair (3, 1). Instead of 1/3, store (1, 3). Two fractions are equal if and only if their reduced forms are identical — and reducing uses only integer division (GCD), which is exact.

The GCD Normalization#

Given two points (x1, y1) and (x2, y2):

1. Compute the raw deltas: dx = x2 - x1, dy = y2 - y1.
2. Compute g = gcd(|dy|, |dx|).
3. Divide both by g: the canonical slope key is (dy // g, dx // g).

Why gcd(|dy|, |dx|) and not gcd(dy, dx)? Because GCD is defined for non-negative integers. Taking absolute values first handles negative deltas correctly.

Sign Normalization — The Hidden Trap#

There is one more subtlety. The slope from A to B is the same line as the slope from B to A, but if you compute deltas naively:

• A to B: dx = 1, dy = -2 — normalized: (-2, 1)
• B to A: dx = -1, dy = 2 — normalized: (2, -1)

These are the same slope, but they produce different keys! The fix: always normalize so the denominator (dx) is positive. If dx < 0, negate both dx and dy. If dx == 0 (vertical line), use a special sentinel key like (1, 0).

Handling Vertical Lines#

When dx = 0, the slope is undefined (vertical line). Use the sentinel (1, 0) — a pair that no normal slope can ever produce since a valid slope with dx = 0 would have been caught by the vertical check, and (1, 0) cannot arise from GCD reduction of any non-vertical pair (a non-vertical pair has dx != 0, so the denominator after reduction is non-zero).

Handling Duplicate Points#

The original LeetCode 149 constraint states all points are unique, so technically you do not need to handle exact duplicates. However, the problem has historically included duplicate points in older test sets, and interviewers will ask about it. The correct handling: track a dupes counter per anchor point. Duplicate points lie on every possible line through the anchor, so they add to the count of every slope group. For each anchor i, the true collinear count for slope s is slope_count[s] + dupes + 1 (the +1 is the anchor itself).

The Full Algorithm#

For each point i (the anchor):

1. Initialize an empty slopes HashMap and a dupes counter.
2. For each other point j:
   • If points[j] == points[i]: increment dupes, continue.
   • Otherwise: compute the normalized slope key, increment slopes[key].
3. The best collinear count through anchor i is max(slopes.values()) + dupes + 1. If slopes is empty (all other points are duplicates), the answer through this anchor is dupes + 1.
4. Track the global maximum across all anchors.

Time: O(n^2) — two nested loops, O(1) work per pair. Space: O(n) — the slopes HashMap has at most n-1 entries per anchor.

Visual Dry Run#

Let us trace through Example 2 in detail:

points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Indices:      0      1      2      3      4      5

We want to find the maximum collinear set. Let us pick anchor = point 0 = (1,1) and compute slopes to all other points.

Anchor: (1, 1)
 
  To (3, 2):  dx=2, dy=1  → gcd(1,2)=1 → key=(1,2)
  To (5, 3):  dx=4, dy=2  → gcd(2,4)=2 → (2/2, 4/2) = key=(1,2)   ← same!
  To (4, 1):  dx=3, dy=0  → gcd(0,3)=3 → (0/3, 3/3) = key=(0,1)
  To (2, 3):  dx=1, dy=2  → gcd(2,1)=1 → key=(2,1)
  To (1, 4):  dx=0, dy=3  → vertical   → key=(1,0)
 
slopes after anchor (1,1):
  {(1,2): 2,  (0,1): 1,  (2,1): 1,  (1,0): 1}
 
max(slopes.values()) + 1 = 2 + 1 = 3

Now anchor = point 1 = (3,2):

Anchor: (3, 2)
 
  To (1, 1):  dx=-2, dy=-1 → dx<0, negate → dx=2, dy=1  → gcd(1,2)=1 → key=(1,2)
  To (5, 3):  dx=2,  dy=1  → gcd(1,2)=1 → key=(1,2)   ← same group!
  To (4, 1):  dx=1,  dy=-1 → gcd(1,1)=1 → key=(-1,1)
  To (2, 3):  dx=-1, dy=1  → dx<0, negate → dx=1, dy=-1 → key=(-1,1)  ← same!
  To (1, 4):  dx=-2, dy=2  → dx<0, negate → dx=2, dy=-2 → gcd(2,2)=2 → key=(-1,1)  ← same!
 
slopes after anchor (3,2):
  {(1,2): 2,  (-1,1): 3}
 
max(slopes.values()) + 1 = 3 + 1 = 4   ← new global max!

Points (1,4), (2,3), (3,2), (4,1) all share the same normalized slope of (-1, 1) from anchor (3,2), giving a count of 4. This is the answer.

Final answer: 4

Common Mistakes#

Mistake 1: Using Float Division for Slope#

This is the most dangerous mistake because it produces wrong answers silently — the code runs, gives almost-correct output, and passes many test cases but fails on edge cases with large coordinates or near-collinear points.

Wrong approach:

slope = dy / dx   # float division — introduces rounding errors
slopes[slope] += 1

Correct approach:

g = gcd(abs(dy), abs(dx))
key = (dy // g, dx // g)   # exact integer fraction — no rounding
slopes[key] += 1

The rule of thumb: any time you need to compare computed values for equality (especially as HashMap keys), prefer integer representations over floats. This is a core principle in computational geometry.

Mistake 2: Forgetting Sign Normalization#

The slope from A to B and from B to A must produce the same key, because they lie on the same line. Without sign normalization, the slope (-1, 2) and the slope (1, -2) are stored as different keys even though they represent the same direction.

Wrong approach: Just divide by GCD without normalizing signs.

Correct approach: After dividing by GCD, ensure the denominator is positive. If dx < 0, multiply both dy and dx by -1. If dx == 0, ensure dy is positive (both are positive since dy > 0 at that point because duplicate points are already handled separately).

Actually, since we iterate j from i+1 to n-1 (only forward), this specific sign issue does not arise in the pairwise-forward approach — but if you ever compute both directions, you must normalize. Many implementations use the outer loop from 0 to n-1 and the inner loop from i+1 to n-1 specifically to avoid this.

Mistake 3: Ignoring the Vertical Line Case#

When dx = 0, the formula dy // gcd(abs(dy), abs(dx)) breaks because gcd(|dy|, 0) = |dy|, giving a key of (1, 0) — which is actually correct! But many implementations forget to handle dx = 0 explicitly and accidentally compute dy / dx as a float division, hitting a ZeroDivisionError or producing inf.

Always handle dx = 0 before computing the slope key. A clean pattern is: g = gcd(abs(dy), abs(dx)) handles this correctly since gcd(k, 0) = k for any positive integer k, giving dy // k = 1 (if dy was normalized to g) and dx // k = 0. Use the same formula uniformly.

Mistake 4: Off-by-One on the Anchor Count#

The count in slopes[key] counts how many other points share that slope with the anchor. The anchor itself is also on the line, so the total collinear count is slopes[key] + 1. Forgetting the +1 gives an answer that is always one less than the correct answer.

Wrong: ans = max(ans, max(slopes.values())) Correct: ans = max(ans, max(slopes.values()) + 1)

Mistake 5: Not Resetting the HashMap Per Anchor#

A fresh slopes HashMap must be created for each anchor point. If you reuse the same map across different anchors, slopes from earlier anchors contaminate the counts for later anchors, producing wildly incorrect results.

Solutions#

Python#

from math import gcd
from collections import defaultdict
from typing import List
 
 
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
 
        # Base case: any 1 or 2 points are always collinear
        if n <= 2:
            return n
 
        ans = 1  # at minimum, one point is always "on a line"
 
        for i in range(n):
            # Fresh slope map for this anchor — MUST reset each iteration
            slopes = defaultdict(int)
            dupes = 0  # points identical to the anchor
 
            for j in range(i + 1, n):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
 
                # Handle duplicate points (same coordinate as anchor)
                if dx == 0 and dy == 0:
                    dupes += 1
                    continue
 
                # Compute GCD of absolute values for normalization
                # gcd(k, 0) = k, so vertical lines (dx=0) are handled correctly:
                #   gcd(|dy|, 0) = |dy|  →  key = (dy/|dy|, 0) = (1, 0) or (-1, 0)
                # We further normalize so dy is positive when dx == 0.
                g = gcd(abs(dy), abs(dx))
 
                # Reduce to canonical form
                norm_dy = dy // g
                norm_dx = dx // g
 
                # Sign normalization: make the denominator (dx) always positive.
                # This ensures slope A->B and slope B->A map to the same key.
                if norm_dx < 0:
                    norm_dy = -norm_dy
                    norm_dx = -norm_dx
                # Special case: vertical line (norm_dx == 0).
                # Ensure norm_dy is always +1 for vertical lines so the key is (1, 0).
                elif norm_dx == 0:
                    norm_dy = abs(norm_dy)
 
                slopes[(norm_dy, norm_dx)] += 1
 
            # The best line through anchor i:
            #   max slope group + duplicates + 1 (the anchor itself)
            if slopes:
                best_through_i = max(slopes.values()) + dupes + 1
            else:
                # All other points were duplicates of anchor i
                best_through_i = dupes + 1
 
            ans = max(ans, best_through_i)
 
        return ans

JavaScript#

/**
 * LeetCode 149 — Max Points on a Line
 *
 * Strategy: For each anchor point i, compute the normalized slope (as a
 * reduced integer fraction) to every other point j. Count slope frequencies
 * in a Map. The maximum frequency + 1 (for the anchor) is the best line
 * through i. Track the global maximum across all anchors.
 *
 * Time:  O(n^2)
 * Space: O(n)
 *
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function(points) {
    const n = points.length;
 
    // Base case: 1 or 2 points are always collinear
    if (n <= 2) return n;
 
    /**
     * Compute GCD of two non-negative integers using Euclidean algorithm.
     * gcd(k, 0) = k by convention — this correctly handles vertical lines.
     */
    const gcd = (a, b) => {
        while (b !== 0) {
            [a, b] = [b, a % b];   // standard Euclidean step
        }
        return a;
    };
 
    let ans = 1;  // at minimum, a single point is "on a line"
 
    for (let i = 0; i < n; i++) {
        // Fresh Map for this anchor — must reset each outer iteration
        const slopes = new Map();
        let dupes = 0;  // points identical to anchor i
 
        for (let j = i + 1; j < n; j++) {
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
 
            // Handle exact duplicate coordinates
            if (dx === 0 && dy === 0) {
                dupes++;
                continue;
            }
 
            // Compute GCD of absolute values
            const g = gcd(Math.abs(dy), Math.abs(dx));
 
            // Reduce to lowest terms
            let normDy = dy / g;
            let normDx = dx / g;
 
            // Sign normalization: ensure denominator (dx) is always positive.
            // This makes the slope representation canonical regardless of direction.
            if (normDx < 0) {
                normDy = -normDy;
                normDx = -normDx;
            } else if (normDx === 0) {
                // Vertical line: fix dy to +1 so all vertical lines share key "1,0"
                normDy = Math.abs(normDy);
            }
 
            // Use a string key since JS Maps use reference equality for objects
            const key = `${normDy},${normDx}`;
            slopes.set(key, (slopes.get(key) || 0) + 1);
        }
 
        // Best line through anchor i: peak slope group + duplicates + 1 (anchor itself)
        let bestThroughI = dupes + 1;  // default if no other distinct points
        for (const count of slopes.values()) {
            bestThroughI = Math.max(bestThroughI, count + dupes + 1);
        }
 
        ans = Math.max(ans, bestThroughI);
    }
 
    return ans;
};

Complexity Analysis#

No approach faster than O(n^2) is known for the general case of this problem. You must inspect every pair of points at least once to determine which pairs might be collinear, and that is already O(n^2) work. Some computational geometry algorithms can do better under special assumptions (all points in convex position, etc.), but for the general LeetCode constraint, O(n^2) is optimal.

Follow-up Questions#

These are real questions that Google and Amazon interviewers raise after you solve the basic problem.

"What if points can have floating-point coordinates?"#

With float coordinates, dx and dy are floats. You can no longer use integer GCD. Options:

1. Round to a fixed precision and use the rounded value as the key. Fragile — precision threshold is problem-dependent.
2. Use a tolerance-based comparison (abs(slope1 - slope2) < epsilon). This makes HashMap usage impossible (HashMap requires exact equality); you would need a different data structure.
3. Scale coordinates to integers by multiplying by a large factor (e.g., 10^9) and rounding. If the problem guarantees a certain precision in the input (e.g., two decimal places), this is reliable.

The correct answer in an interview: mention that floating-point coordinates fundamentally break exact hashing, explain the integer GCD approach for rational coordinates, and note that with arbitrary floats the problem requires a different algorithmic strategy (such as RANSAC for approximate collinearity in computer vision applications).

"What if n is 10 million — can you do better than O(n^2)?"#

For n = 300 (LeetCode constraint), O(n^2) is fine. For n = 10,000,000, O(n^2) = 10^14 operations — infeasible.

Known improvements:

• Randomized approaches (RANSAC): Pick two random points, find the line, count collinear points, repeat. Expected runtime depends on the fraction of inliers. If many points are collinear, RANSAC converges quickly.
• Dual transform: Map each point to a line in dual space. Collinear points in primal space become concurrent lines in dual space. Count line intersections using a sweep line algorithm in O(n^2 log n), which is not better in the worst case but has practical advantages.
• Hashing with geometric hashing: Precompute all pairwise slopes and sort them. O(n^2 log n) time but enables fast queries for a given slope.

In practice, for massive n, approximate algorithms (like RANSAC) are preferred because exact O(n^2) is unavoidable for the general problem.

"What if you need to return the actual line, not just the count?"#

Track not just the maximum count but also the key (norm_dy, norm_dx) and the anchor i that produced it. To reconstruct the line:

• Direction vector: (norm_dx, norm_dy).
• A point on the line: points[i].
• Line equation: norm_dy * (x - xi) = norm_dx * (y - yi), rearranged to standard Ax + By + C = 0 form.

"How would you detect if any three points are collinear — a simpler version?"#

This is a warm-up version of the problem. For three specific points A, B, C, use the cross product:

cross = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)

If cross == 0, the three points are collinear. No HashMap needed — pure O(1) math. This works because the cross product equals the signed area of the triangle formed by the three points; zero area means collinear. This is worth mentioning as the foundation for understanding why the full problem requires a different approach.

"What if all points are guaranteed to be on a circle?"#

On a circle, at most 2 points can be collinear with the center (a diameter). Among points on the circumference, any 3 determine a unique circle — so no 3 points on a circle are collinear (unless they happen to lie on a diameter, which allows only 2 points on the circle to be collinear). The answer would always be 2, unless the input includes the center. This is a trick question designed to see if you think geometrically rather than just running an algorithm.

This Pattern Solves#

The general abstraction: fix an anchor, compute a normalized relationship key to every other element, use a HashMap to find the most frequent key. This "anchor + normalized key" pattern solves many geometry problems where you need to group objects by a computed property.

Key Takeaways#

• Never use float division for slope — floating-point precision errors cause false mismatches. Use a GCD-reduced fraction (dy // g, dx // g) as the HashMap key for exact comparisons.
• Sign normalization is required: ensure the denominator dx is always non-negative (or the canonical dy is positive when dx == 0) so the same slope never gets two different keys.
• Handle duplicate points separately — track them per anchor and add their count to every slope group for that anchor.
• The algorithm is O(n^2) — for each of n anchor points, compute slopes to all other n-1 points using a HashMap.
• The final answer for each anchor is max_slope_count + duplicates + 1 (the +1 is for the anchor itself).
• Vertical lines have dx = 0; normalize as (1, 0) as the key to avoid division by zero.
• This pattern (anchor + normalized key + HashMap) generalizes to LC 447 (Number of Boomerangs) and other geometry problems where you group by a computed relationship to one point.