Watch 10 video solutions for Max Points on a Line, a hard level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 25,713 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 300points[i].length == 2-104 <= xi, yi <= 104points are unique.Problem Overview: Given a list of 2D points, determine the maximum number of points that lie on the same straight line. Any line can be defined by two points, but the challenge is efficiently grouping all points that share the same slope.
Approach 1: Using Slope Calculation with Hashmap (O(n^2) time, O(n) space)
Fix one point as an anchor and compute the slope between this point and every other point. Points that lie on the same line relative to the anchor will share the same slope. Store slope frequencies in a hash map while iterating through the remaining points. Special handling is required for vertical lines (undefined slope) and duplicate points. After processing each anchor, the maximum slope frequency plus duplicates gives the number of collinear points through that anchor.
This method works because a line through a fixed point is uniquely determined by its slope. Using a hash lookup lets you group points with identical slopes in constant time. The overall complexity becomes O(n^2) since every point compares with all others once. This approach relies heavily on concepts from Hash Table, Geometry, and Array processing.
Approach 2: Using Line Equation with Hashmap (O(n^2) time, O(n^2) space)
Instead of fixing an anchor, compute the full line equation formed by every pair of points. A line can be represented in normalized form Ax + By + C = 0. For each pair of points, derive coefficients A, B, and C, then normalize them using the greatest common divisor so equivalent lines share the same representation. Store each line in a hashmap and track which points belong to it.
All pairs that produce the same normalized equation correspond to the same geometric line. Counting the unique points mapped to each line yields the answer. This approach is mathematically clean and avoids slope edge cases like vertical lines, but it uses more memory because many line equations are stored. Pair generation also keeps the runtime at O(n^2).
Recommended for interviews: The slope-hashmap approach is the one most interviewers expect. It demonstrates strong understanding of slope normalization, hash-based counting, and handling duplicates. A brute-force triple check would be O(n^3) and usually too slow, while the anchor-based slope grouping achieves the optimal O(n^2) time with manageable space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slope Calculation with Hashmap (Anchor Point) | O(n^2) | O(n) | Best general solution for interviews. Efficiently groups points sharing the same slope relative to an anchor. |
| Line Equation Normalization with Hashmap | O(n^2) | O(n^2) | Useful when representing lines explicitly using normalized equations and avoiding slope edge cases. |