Max Points on a Line

Difficulty: Hard
Topics: Array, Hash Table, Math, Geometry
Link: https://leetcode.com/problems/max-points-on-a-line/

Problem Description

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.

Solution

1. Problem Deconstruction (500+ words)

Technical Restatement

Given a finite set ( P = {p_1, p_2, \dots, p_n} ) of distinct points in the Euclidean plane, where each point ( p_i ) is represented by its Cartesian coordinates ((x_i, y_i)), determine the cardinality of the largest subset ( L \subseteq P ) such that all points in ( L ) are collinear—i.e., there exists a straight line ( \ell ) in the plane with ( L \subset \ell ). The output is the integer ( \max_{L \subseteq P, \text{collinear}} |L| ).

Beginner-Friendly Restatement

Imagine you have several dots on a graph paper. Your task is to find the largest group of dots that can be connected by a single straight line without bending. You need to count how many dots are in that group. The dots are all at different positions.

Mathematical Formulation

Let ( P = {(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)} ) with ( n \ge 1 ). For any two distinct points ( (x_i, y_i) ) and ( (x_j, y_j) ), define the set of points collinear with them as:
[ C(i,j) = {(x_k, y_k) \in P \mid (y_k - y_i)(x_j - x_i) = (y_j - y_i)(x_k - x_i)}. ]
The problem requires computing:
[ \max_{\substack{i,j \ i \neq j}} |C(i,j)| \quad \text{or} \quad 1 \text{ if } n = 1. ]
Alternatively, using the slope‑intercept representation: a line is defined by ( y = mx + b ) (non‑vertical) or ( x = c ) (vertical). The condition for three points to be collinear is that the slopes between pairs are equal:
[ \frac{y_j - y_i}{x_j - x_i} = \frac{y_k - y_i}{x_k - x_i}, ]
with careful handling of vertical lines (infinite slope) and duplicate points (not present here).

Constraint Analysis

1 <= points.length <= 300
The input size is modest, allowing polynomial solutions up to (O(n^3)) in the worst case. However, an (O(n^3)) brute‑force approach (checking all triples) becomes borderline for (n=300) (~27 million operations), which is acceptable in many environments but can be optimized. An (O(n^2)) solution is preferred and easily runs within limits.
points[i].length == 2
Each point is strictly 2‑dimensional; no degenerate higher‑dimensional cases need consideration.
-10^4 <= xi, yi <= 10^4
Coordinates are integers within a bounded range. This allows exact rational arithmetic without floating‑point precision issues if we use integer representations for slopes (e.g., reduced fractions of differences). However, large coordinate values can cause overflow when computing products (e.g., ((y_j-y_i)*(x_k-x_i))), so 64‑bit integers (or language‑specific big integers) are recommended.
All the points are unique.
No duplicate points exist, simplifying slope‑based grouping: each point pair defines a unique line. Without duplicates, the minimum answer is 1 (if no two points are collinear) or 2 (if at least one pair exists). However, if duplicates were allowed, the same line could be defined by multiple identical points, requiring special handling (count duplicates separately). This constraint removes that complexity.

Hidden Edge Cases

Single point: Answer is 1.
All points distinct but collinear: Answer is (n).
Vertical lines: Slope is infinite; must be handled separately (e.g., using a sentinel value or a different key).
Horizontal lines: Slope is zero; works with fraction reduction.
Points with same x but different y: vertical line.
Large coordinate differences: Risk of integer overflow when computing slope as a fraction; use greatest common divisor (GCD) to reduce numerator and denominator to smallest terms.
Parallel lines with same slope but different intercepts: Not an issue because we group by slope and intercept together.

2. Intuition Scaffolding

Analogies

Real‑World Metaphor (Construction/Planning)
Imagine you are a surveyor placing stakes in a field. You want to find the longest straight fence that can pass through as many stakes as possible without moving them. You try all possible pairs of stakes as anchor points and see how many other stakes align with that imaginary fence line.
Gaming Analogy (Strategy Game)
In a turn‑based tactics game, units can attack in straight lines. You want to position your archers so that their line‑of‑shot hits as many enemies as possible. By checking every two enemies, you determine the line that pierces through the most targets, maximizing your area‑effect attack.
Math Analogy (Clustering in Parameter Space)
Each line in the plane is characterized by parameters (slope and intercept). Points lying on the same line correspond to the same parameter pair. Thus, the problem reduces to finding the most frequent (slope, intercept) pair among all lines defined by point pairs. However, we must avoid counting the same line multiple times; we can fix one point and consider all lines through it, counting slopes.

Common Pitfalls

Using floating‑point slopes leads to precision errors when comparing equality. Solution: Represent slopes as reduced fractions (dy/dx) using GCD, storing numerator and denominator as a pair.
Forgetting vertical lines where dx = 0. Need a special representation (e.g., (inf, x‑intercept) or a sentinel string).
Counting the same line multiple times when iterating over all pairs without grouping efficiently. The optimal method fixes a point and checks slopes with all other points, ensuring lines through that point are counted together.
Overlooking the case when all points are distinct and no three are collinear; then the answer is 2 (if at least two points exist).
Not handling the single‑point case, which should return 1.
Integer overflow when computing dy*dx or products in collinearity checks. Use 64‑bit integers and reduce fractions early.

3. Approach Encyclopedia

Approach 1: Brute Force (Triple Check)

Idea: For each pair of points, check all other points to see if they lie on the same line.
Why it works: Three points are collinear if the slope between the first two equals the slope between the first and third (or equivalently, the area of the triangle they form is zero).
How:

Loop over all ordered pairs (i, j) with i < j.
Initialize count = 2 (the two points).
For every other point k not equal to i or j, check collinearity using the cross‑product formula:
(y_j - y_i)*(x_k - x_i) == (y_k - y_i)*(x_j - x_i)
Update a global maximum.

Pseudocode:

max_points = 1
for i = 0 to n-1:
    for j = i+1 to n-1:
        count = 2
        for k = 0 to n-1:
            if k != i and k != j:
                if (points[j].y - points[i].y)*(points[k].x - points[i].x) == 
                   (points[k].y - points[i].y)*(points[j].x - points[i].x):
                    count += 1
        max_points = max(max_points, count)
return max_points

Complexity Proof:

Time: (O(n^3)). There are (\binom{n}{2} = O(n^2)) pairs, and for each we iterate over (O(n)) other points, giving (O(n^3)).
Space: (O(1)) extra variables.

Visualization:

Points: (1,1), (2,2), (3,3), (1,2)

Pair (1,1)-(2,2): slope 1
   Check (3,3): slope 1 → collinear (count=3)
   Check (1,2): slope (1)/(0) vertical? No → not collinear
   max = 3

Pair (1,1)-(3,3): slope 1
   Check (2,2): collinear (count=3)
   Check (1,2): not collinear
   max remains 3

... (other pairs yield ≤3)

Approach 2: Slope‑Map with Fixed Point (Optimized O(n²))

Idea: For each point i, compute the slope between i and every other point j. The slope (with a unique representation) defines a line through i. Points with the same slope relative to i lie on the same line through i. Count frequencies of slopes.
Why it works: All lines that contain point i are captured by slopes from i to others. The maximum frequency of a slope (+1 for point i itself) gives the maximum number of points on a line through i. Repeating for all i covers all possible lines because any line containing at least two points will be considered when one of those points is the anchor i.

Pseudocode:

max_points = 1
for i = 0 to n-1:
    slope_map = {}
    for j = i+1 to n-1:
        dx = points[j].x - points[i].x
        dy = points[j].y - points[i].y
        if dx == 0:
            key = "vertical"
        else:
            g = gcd(dx, dy)
            dx /= g; dy /= g   # reduce to simplest form
            key = (dy, dx)     # use tuple of integers
        slope_map[key] = slope_map.get(key, 0) + 1
    max_through_i = max(slope_map.values(), default=0) + 1
    max_points = max(max_points, max_through_i)
return max_points

Complexity Proof:

Time: (O(n^2 \log M)) where (M) is the range of coordinates. The GCD computation takes (O(\log M)) time.
Space: (O(n)) for the hash map storing at most (n-1) slopes.

Visualization:

Points: A(1,1), B(2,2), C(3,3), D(1,2)

Anchor A:
   A→B: dx=1, dy=1 → slope (1,1)
   A→C: dx=2, dy=2 → reduced (1,1)
   A→D: dx=0, dy=1 → vertical
   Slope map: {(1,1):2, vertical:1}
   max_through_A = 2+1 = 3

Anchor B:
   B→A: (1,1) reduced (1,1)
   B→C: (1,1)
   B→D: (-1,1) reduced (-1,1)
   map: {(1,1):2, (-1,1):1} → max = 2+1=3

Anchor C: similarly max=3
Anchor D: slopes to others are distinct → max=1+1=2
Global max = 3

Approach 3: Optimized with Early Exit and Duplicate Handling (if duplicates allowed)

Not needed here because points are unique, but we can note: if duplicates existed, we would count duplicates separately and add them to each slope count.

4. Code Deep Dive

We implement the optimal O(n²) slope‑map approach.

from collections import defaultdict
from math import gcd

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    
    max_points = 0
    
    for i in range(n):
        # For each anchor point i
        slope_count = defaultdict(int)
        # We'll count slopes from i to all j > i
        # But actually we need to consider all j != i; however, to avoid double counting,
        # we can iterate j from i+1 to n-1. However, note that lines through i may be counted
        # when i is the anchor, so we don't miss any line.
        # However, we must also count the point i itself, so total points on line = count + 1.
        
        # To handle the case where multiple points coincide (not in this problem), we could
        # add a duplicate counter, but constraints say unique.
        
        for j in range(i+1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            
            # Reduce to simplest form using GCD
            if dx == 0:
                # Vertical line: use a sentinel, e.g., (None, points[i][0])
                # But we need a hashable key. Use a tuple (None, x_intercept) or just 'inf'
                # However, to avoid mixing with other vertical lines from different x, we must
                # encode the x-coordinate as well.
                # Actually, for a given anchor i, vertical lines are all the same (all have dx=0),
                # but they are the same line only if the x-coordinate is the same.
                # Wait: For anchor i, any point j with dx=0 means the line through i and j is vertical.
                # All such points j share the same x-coordinate (equal to points[i][0])? Not necessarily:
                # If i has x=1, and j has x=1, then dx=0. But another point k with x=2 would give dx=1, not 0.
                # So for a fixed i, all points j with dx=0 have the same x as i. Therefore, all vertical lines from i are the same line.
                # So we can use a single key for vertical.
                # However, if duplicates were allowed, we might have multiple vertical lines through i? No, through a given point there is only one vertical line.
                # So key for vertical can be anything unique, e.g., "inf".
                key = (0, 0)  # Some use (0,0) or "inf". But to differentiate from horizontal, we need a unique representation.
                # Common practice: use (None, None) or "vertical". But we want a tuple that is hashable.
                # Let's use (0, 0) and treat it specially? Actually, we can use (0, 1) for vertical? Not good.
                # Better: use a string "inf" or a tuple with None.
                # However, to be consistent with reduced fraction representation, we can represent slope as a tuple (dy, dx) and for dx=0, we can use (1, 0) after reducing? But dy/dx when dx=0 is infinite, so we cannot reduce because gcd(0, dx) is dx. Actually, when dx=0, dy can be any value, but we can set the key to (1, 0) if dy>0? But if dy=0, that would be the same point (but duplicates not allowed). So for dx=0, we can set key = (1, 0) if dy>0, and (-1,0) if dy<0? But actually, if dx=0, the line is vertical regardless of dy sign. So we can just use (0, 0) as a sentinel.
                # However, to avoid collisions with a reduced fraction that happens to be (0,0) (which should not occur because dy, dx are not both zero), we can use None.
                key = None  # But None is not a tuple, but it's hashable.
            else:
                g = gcd(dx, dy)
                # Reduce to simplest form, also ensure consistent sign (e.g., make dx positive).
                dx //= g
                dy //= g
                # To have a canonical representation, we can enforce that dx > 0, or if dx == 0 then treat separately.
                # For dx != 0, we can make dx positive.
                if dx < 0:
                    dx = -dx
                    dy = -dy
                key = (dy, dx)
            slope_count[key] += 1
        
        # After counting slopes from i, find the maximum frequency
        current_max = max(slope_count.values(), default=0)
        # Points on the line = current_max (number of other points on that line) + 1 (the anchor i)
        max_points = max(max_points, current_max + 1)
    
    return max_points

Line‑by‑Line Annotations:

def maxPoints(points): – Function definition.
n = len(points) – Store number of points.
if n <= 2: return n – Base case: 1 or 2 points always lie on the same line.
max_points = 0 – Initialize global maximum.
for i in range(n): – Loop over each point as anchor.
slope_count = defaultdict(int) – Map from slope representation to frequency.
for j in range(i+1, n): – Compare with every point after i to avoid double counting the same line (since line through i and j will be counted when i is anchor).
dx = points[j][0] - points[i][0] – Difference in x‑coordinates.
dy = points[j][1] - points[i][1] – Difference in y‑coordinates.
Vertical line handling: If dx == 0, we assign a special key None to represent infinite slope.
Non‑vertical lines: Compute GCD of dx and dy to reduce the fraction to simplest form, ensuring a canonical representation. The reduction ensures that identical slopes have the same key.
Canonical sign: We force dx > 0 by negating both if dx is negative, so that slopes like (1,2) and (-1,-2) become identical.
key = (dy, dx) – Store as a tuple (numerator, denominator).
slope_count[key] += 1 – Increment count for this slope.
current_max = max(slope_count.values(), default=0) – Find the most frequent slope for anchor i. If no slopes (i.e., only one point), default to 0.
max_points = max(max_points, current_max + 1) – Update global max: add 1 for anchor i.
return max_points – Return result.

Edge Case Handling:

Single point: Handled by base case (returns 1).
Two points: Returns 2.
Vertical lines: Special key None groups all vertical lines from anchor i.
Large coordinates: GCD reduction keeps numbers small; using integer arithmetic avoids precision issues.
All points collinear: For any anchor i, all slopes will be identical, so current_max = n-1, result n.
No three collinear: For each anchor, all slopes distinct, so current_max = 1, result max over i is 2.

5. Complexity War Room

Hardware‑Aware Analysis

Time: (O(n^2 \log M)) with (n \le 300), worst‑case operations ~ (90,000) slope computations, each with a GCD taking (O(\log M)) where (M \le 2\times10^4). Total operations ~ (300^2 \times \log(20000) \approx 90,000 \times 15 = 1.35\times10^6), which is trivial on modern CPUs (under 0.01 seconds).
Space: Hash map stores at most (n-1) entries (~300). Memory usage ~ a few KB, fits in L1 cache.
Integer size: Coordinates up to (10^4), differences up to (2\times10^4), products up to (4\times10^8) (fits in 32‑bit signed). GCD uses Euclidean algorithm on 32‑bit numbers, fast.

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force (triple loop)	O(n³)	O(1)	9/10 (simple)	❌ Acceptable only for n≤100
Slope‑Map with Fixed Point	O(n² log M)	O(n)	8/10 (needs GCD)	✅ Recommended
Further optimized (sort slopes)	O(n² log n)	O(n)	7/10 (more complex)	⚠️ Overkill

6. Pro Mode Extras

Variants

Duplicates Allowed
If points may be duplicate, we must count duplicates separately. When choosing anchor i, we count duplicates of i and add that count to every slope bucket (since duplicates lie on every line through i). Alternatively, we can pre‑count duplicates per coordinate and adjust.
Maximum Points on a Line with Weighted Points
Each point has a weight; find the line maximizing the sum of weights of points on it. This requires modifying the slope‑map to store sums instead of counts.
Three‑Dimensional Version
Points in 3D space, find maximum collinear points. The condition becomes direction vectors proportional; similar slope‑map idea using 3D direction vectors reduced to simplest integer triple.
Maximum Points on a Circle
Given points, find the maximum number of points on the same circle. Much harder: circles are defined by three points, leading to O(n³) approaches.

Interview Cheat Sheet

First, mention the brute force O(n³) approach to show understanding, but note it’s inefficient for large n.
Immediately propose the O(n²) slope‑map approach with fixed anchor.
Emphasize handling of vertical lines and floating‑point issues – use reduced fractions with GCD.
Mention the base cases (n ≤ 2).
Discuss complexity and why it’s optimal (must look at all pairs).
If time, discuss variants (duplicates, weighted).
Practice drawing a small example on the board to illustrate slope grouping.

Key formula to remember:
Collinearity test: (y2 - y1)*(x3 - x1) == (y3 - y1)*(x2 - x1)
Slope reduction: gcd(dx, dy) to get canonical representation.

Final tip: In interviews, always ask about duplicate points even if not in the problem statement, to show thoroughness.

#149 - Max Points on a Line