Max Points on a Line

Hard
686.

Max Points on a Line

Max Points on a Line is a hard coding problem on hash table, math and geometry, asked in Amazon, Google, Apple and Twitter interviews.

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 <= 300
  • points[i].length == 2
  • -10000 <= x, y <= 10000
  • All points are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function(points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 300
  • points[i].length == 2
  • -10000 <= x, y <= 10000
  • All points are distinct.

Hints for Max Points on a Line

  1. Hint 1

    Every line through at least two points passes through some point i — so fix i and group the others by direction.

  2. Hint 2

    Floating-point slopes are the classic trap: vertical lines divide by zero, and rounding merges distinct slopes.

  3. 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

  1. For each anchor i, walk every other point j and form (dx, dy) = (xj - xi, yj - yi).
  2. Divide both by gcd(|dx|, |dy|) so parallel vectors reduce to the same pair.
  3. Flip the sign so that dx > 0, or dx == 0 with dy > 0 — this merges a direction with its opposite.
  4. 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 / dx as 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 guarding g == 0 costs nothing.
  • One or two points trivially lie on a line — return n directly.

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 best

Java

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