Max Points on a Line — Solution in Python, Java & C++
Max Points on a Line solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Max Points on a Line is a hard coding problem on hash table, math and geometry, asked in Amazon, Google, Apple and Twitter interviews.
- Difficulty: Hard
- Topics: Hash Table, Math, Geometry
- Asked at: Amazon, Google, Apple, Twitter, Sprinklr
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given points on a plane, return the maximum number of them that lie on the same straight line.
Example 1
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Explanation: All three sit on the line y = x.
Example 2
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: (1,4), (2,3), (3,2) and (4,1) are collinear.
Example 3
Input: points = [[0,0]]
Output: 1
Constraints
1 <= points.length <= 300points[i].length == 2-10000 <= x, y <= 10000All points are distinct.
Hints for Max Points on a Line
Hint 1
Every line through at least two points passes through some point
i— so fixiand group the others by direction.Hint 2
Floating-point slopes are the classic trap: vertical lines divide by zero, and rounding merges distinct slopes.
Hint 3
Normalise each direction vector
(dx, dy)by its gcd and fix a canonical sign so that(1,2)and(-1,-2)are the same key.
How to solve Max Points on a Line
Anchor on each point and bucket the other points by the reduced direction vector to it. The largest bucket plus the anchor itself is the best line through that anchor; the maximum over anchors is the answer.
Approach
- For each anchor
i, walk every other pointjand form(dx, dy) = (xj - xi, yj - yi). - Divide both by
gcd(|dx|, |dy|)so parallel vectors reduce to the same pair. - Flip the sign so that
dx > 0, ordx == 0withdy > 0— this merges a direction with its opposite. - Tally the normalised keys; the best count plus one (for the anchor) is a candidate answer.
Why it works
Two points lie on a line through the anchor exactly when their direction vectors from it are parallel, and the gcd-reduced sign-normalised vector is a canonical representative of a direction. Since every line with two or more points contains an anchor that is examined, no line is missed.
Complexity
- Time —
O(n² log V) - Space —
O(n)
Pitfalls
- Using
dy / dxas a double breaks on vertical lines and can equate slopes that differ in the last bits. - Without sign normalisation, points on opposite sides of the anchor land in different buckets and the count halves.
gcd(0, 0)never arises because the points are distinct, but guardingg == 0costs nothing.- One or two points trivially lie on a line — return
ndirectly.
Reference solution
Python
from math import gcd
from typing import List
def maxPoints(points: List[List[int]]) -> int:
n = len(points)
if n <= 2:
return n
best = 1
for i in range(n):
slopes = {}
for j in range(n):
if i == j:
continue
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
g = gcd(abs(dx), abs(dy)) or 1
dx //= g
dy //= g
if dx < 0 or (dx == 0 and dy < 0):
dx, dy = -dx, -dy
key = (dx, dy)
slopes[key] = slopes.get(key, 0) + 1
best = max(best, slopes[key] + 1)
return bestJava
public static int maxPoints(int[][] points) {
int n = points.length;
if (n <= 2) return n;
int best = 1;
for (int i = 0; i < n; i++) {
Map<String, Integer> slopes = new HashMap<>();
for (int j = 0; j < n; j++) {
if (i == j) continue;
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int g = gcdPoints(Math.abs(dx), Math.abs(dy));
if (g == 0) g = 1;
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
String key = dx + "/" + dy;
int c = slopes.getOrDefault(key, 0) + 1;
slopes.put(key, c);
if (c + 1 > best) best = c + 1;
}
}
return best;
}
static int gcdPoints(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}C++
static int gcdPoints(int a, int b) {
while (b != 0) { int t = a % b; a = b; b = t; }
return a;
}
int maxPoints(vector<vector<int>>& points) {
int n = (int) points.size();
if (n <= 2) return n;
int best = 1;
for (int i = 0; i < n; i++) {
map<pair<int, int>, int> slopes;
for (int j = 0; j < n; j++) {
if (i == j) continue;
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int g = gcdPoints(abs(dx), abs(dy));
if (g == 0) g = 1;
dx /= g;
dy /= g;
if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
int c = ++slopes[{ dx, dy }];
if (c + 1 > best) best = c + 1;
}
}
return best;
}JavaScript
var maxPoints = function(points) {
var n = points.length;
if (n <= 2) return n;
var gcd = function(a, b) {
while (b !== 0) {
var t = a % b;
a = b;
b = t;
}
return a;
};
var best = 1;
for (var i = 0; i < n; i++) {
var slopes = {};
for (var j = 0; j < n; j++) {
if (i === j) continue;
var dx = points[j][0] - points[i][0];
var dy = points[j][1] - points[i][1];
var g = gcd(Math.abs(dx), Math.abs(dy));
if (g === 0) g = 1;
dx = dx / g;
dy = dy / g;
if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
var key = dx + "/" + dy;
slopes[key] = (slopes[key] === undefined ? 0 : slopes[key]) + 1;
if (slopes[key] + 1 > best) best = slopes[key] + 1;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets