Max Points on a Line
Last Updated: March 28, 2026
Understanding the Problem
We are given a set of 2D points and need to find the largest subset of points that all lie on the same straight line. Two points always define a line, so the challenge is figuring out how to group points by the lines they share and find the group with the most points.
The key observation is this: if we fix one point as an "anchor," then every other point defines a direction (slope) from that anchor. Points that share the same slope from the anchor are all collinear with it. So the problem reduces to: for each anchor point, count how many other points share the same slope, and track the maximum.
The tricky part is representing slopes. Using floating-point division (dy/dx) introduces precision errors. Instead, we can represent the slope as a reduced fraction (dy/dx in lowest terms), which gives us an exact, hashable key.
Key Constraints:
1 <= points.length <= 300--> With n up to 300, an O(n^3) brute force is feasible (27 million operations). An O(n^2) approach is comfortable. No need for anything subquadratic.-10^4 <= xi, yi <= 10^4--> Coordinates are bounded integers. Differences fit in a standard 32-bit int. No overflow concerns with basic arithmetic.All the points are unique--> We don't need to handle duplicate points as a special case. Every pair of distinct points defines a unique line.
Approach 1: Brute Force (Check Every Triplet)
Intuition
The most straightforward way to think about this: a line is defined by two points, and we can check whether a third point lies on the same line. So we could pick every pair of points, then count how many of the remaining points are collinear with that pair.
To check if three points (x1,y1), (x2,y2), (x3,y3) are collinear, we use the cross product formula: (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1). If this holds, all three points lie on the same line. No division needed, no floating-point issues.
Algorithm
- If there are fewer than 3 points, return the number of points (1 or 2 points are trivially collinear).
- For every pair of points (i, j), count how many other points k are collinear with i and j using the cross product test.
- Track the maximum count across all pairs. The count for each pair starts at 2 (for i and j themselves) plus however many k-points are collinear.
- Return the maximum count.
Example Walkthrough
Code
- Time Complexity: O(n^3). We iterate over all pairs of points (O(n^2)), and for each pair, we check every other point (O(n)).
- Space Complexity: O(1). We only use a few integer variables. No additional data structures.
This approach works but has redundant computation. Many pairs define the same line, so we recount collinear points multiple times. What if we fixed one anchor point and grouped all other points by their slope?
Approach 2: Slope Grouping with Hash Map (Optimal)
Intuition
Instead of checking every triplet, fix one point as an anchor. Every other point defines a slope from that anchor. If two other points share the same slope relative to the anchor, all three are collinear.
For each anchor, build a hash map where the key is the slope and the value is how many points share that slope. The answer for this anchor is the largest group plus one (for the anchor itself). Do this for every anchor and take the global maximum.
The subtlety is representing the slope. Using dy/dx as a float leads to precision bugs. Instead, represent the slope as (dy, dx) reduced to lowest terms by GCD, with sign normalization so that dx is always non-negative (and if dx == 0, dy is positive).
Collinearity is about shared slopes. If points B and C both have the same slope from anchor A, then A, B, and C must be collinear. By grouping all points by their slope relative to a fixed anchor, we transform a geometric problem into a counting problem.
The GCD-based slope representation avoids floating-point issues entirely. Two slopes are equal if and only if their reduced fractions are identical. The sign normalization ensures that opposite directions (going from A to B vs B to A) produce the same key.
Algorithm
- If there are fewer than 3 points, return the number of points.
- For each point i (the anchor):
a. Create an empty hash map: slope to count.
b. For each other point j, compute dy and dx, reduce by GCD, normalize sign, and increment the slope count.
c. The best count through anchor i is the max value in the slope map plus 1.
- Return the global maximum across all anchors.
Example Walkthrough
Code
- Time Complexity: O(n^2). We iterate over each of the n points as an anchor. For each anchor, we iterate over all other n-1 points to compute slopes and update the hash map.
- Space Complexity: O(n). The slope hash map for each anchor can hold at most n-1 entries. We clear and rebuild it for each anchor.