Max Points on a Line
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 grouping points by the lines they share and finding the group with the most points.
If we fix one point as an anchor, every other point defines a direction (slope) from that anchor. Points that share the same slope from the anchor are all collinear with it. The problem reduces to: for each anchor point, count how many other points share the same slope, and track the maximum.
The hard part is representing slopes. Using floating-point division (dy/dx) introduces precision errors. Instead, we represent the slope as a reduced fraction (dy/dx in lowest terms), which gives an exact, hashable key.
Key Constraints:
1 <= points.length <= 300--> With n up to 300, an O(n^3) brute force runs at most about 27 million operations, which is fast enough. An O(n^2) approach is well within limits.-10^4 <= xi, yi <= 10^4--> Coordinate differences range from -210^4 to 210^4. The collinearity cross product multiplies two such differences and subtracts, giving a magnitude up to 810^8. That stays under the 32-bit signed limit of about 2.110^9, so a 32-bit int does not overflow. The brute-force code uses 64-bit products in C++, C#, and Rust anyway, as a safe default for this kind of geometric arithmetic.All the points are unique--> There are no duplicate points to handle as a special case. Every pair of distinct points defines a unique line.
Approach 1: Brute Force (Check Every Triplet)
Intuition
A line is defined by two points, and we can test whether a third point lies on that same line. So we 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 test: (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1). The two sides compare the slope from point 1 to point 2 against the slope from point 1 to point 3, cross-multiplied to avoid division. When they are equal, the three points lie on one line. No division, no floating-point error.
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 recounts collinear points many times, since every pair on the same line repeats the same scan. The next approach fixes one anchor point and groups all other points by their slope, which collapses the inner work from one pass per pair to one pass per anchor.
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 best line through this anchor holds the largest group plus one (for the anchor itself). Repeat for every anchor and take the global maximum.
The slope representation needs care. 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).
Two reduced fractions (dy/g, dx/g) are equal exactly when the original directions are parallel, so equal keys imply collinearity with the anchor. Direction is the complication: from anchor A, a point at offset (2, 1) and a point at offset (-2, -1) lie on the same line but produce opposite raw fractions. Forcing dx >= 0 (and dy > 0 when dx == 0) maps both to a single key, so antiparallel offsets collapse together. With unique points there is no zero offset to worry about, so every other point contributes exactly one slope.
Algorithm
- If there are fewer than 3 points, return the number of points.
- For each point i (the anchor):
- Create an empty hash map: slope to count.
- For each other point j, compute dy and dx, reduce by GCD, normalize sign, and increment the slope count.
- 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.