LeetCode 149 - Max Points on a Line

LeetCode Problem 149

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Geometry

Solution

Problem Understanding

The problem gives us a list of points on a 2D coordinate plane. Each point is represented as [x, y], where x and y are integer coordinates. Our task is to determine the maximum number of points that lie on the same straight line.

In other words, among all possible lines that can be formed using the given points, we want to find the line that passes through the largest number of points.

For example, if the points are:

[[1,1],[2,2],[3,3]]

all three points lie on the line y = x, so the answer is 3.

The input size is relatively small, at most 300 points, but the challenge comes from correctly identifying when multiple points are collinear. Floating point arithmetic can easily introduce precision errors, especially when dealing with slopes like 1/3 or 2/6. Because of this, a robust solution must represent slopes carefully.

The constraints also guarantee that all points are unique. This simplifies the implementation because we never need to handle duplicate points occupying the exact same coordinate.

Several edge cases are important:

• Vertical lines, where x2 - x1 = 0, produce undefined slopes if handled using division.
• Horizontal lines, where the slope is 0, must be represented consistently.
• Negative slopes must normalize correctly so that equivalent slopes map to the same representation.
• Multiple points may produce mathematically equivalent slopes like 2/4 and 1/2, so reduction using GCD is necessary.
• Very small inputs, such as a single point, must still return a valid answer.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible pair of points and determine which other points lie on the same line.

For every pair (i, j), we can compute the line passing through them. Then we iterate through all remaining points and check whether each point lies on that line.

One way to check collinearity is using the area formula:

(x2 - x1)(y3 - y1) == (y2 - y1)(x3 - x1)

If this equality holds, the three points are collinear.

This method is correct because every valid line is determined by at least two points, and we explicitly verify every point against every possible line.

However, the complexity becomes extremely large:

• There are O(n^2) point pairs.
• For each pair, we may scan all n points.

This results in O(n^3) time complexity, which becomes inefficient for n = 300.

Optimal Approach

The key insight is that if we fix one point as an anchor, every other point determines a slope relative to that anchor.

Points that share the same slope with respect to the anchor must lie on the same line.

For example, suppose the anchor point is (1,1):

Other Point	Slope
(2,2)	1
(3,3)	1
(4,5)	4/3

The first two points share the same slope, meaning all three points are collinear.

Instead of checking every triplet explicitly, we:

1. Fix an anchor point.
2. Compute slopes to every other point.
3. Count how many times each slope appears.
4. The most frequent slope represents the largest line through that anchor.

To avoid floating point precision issues, slopes are stored as reduced fractions:

dy / dx

reduced using the greatest common divisor.

This transforms the problem into a hash map frequency counting problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every line against every point
Optimal	O(n²)	O(n)	Uses slope frequency counting with hash maps

Algorithm Walkthrough

1. Handle small inputs immediately.

If the number of points is 0, 1, or 2, the answer is simply the number of points because any set of at most two points is always collinear. 2. Iterate through each point as the anchor point.

For every point points[i], we will compute slopes from this anchor to all later points. 3. Create a hash map for slope frequencies.

The key idea is that points lying on the same line relative to the anchor share the same slope.

The hash map stores:

slope -> count

4. Compute normalized slope representations.

For two points:

(x1, y1)
(x2, y2)

compute:

dx = x2 - x1
dy = y2 - y1

Then reduce both using the greatest common divisor:

gcd_value = gcd(dx, dy)
dx /= gcd_value
dy /= gcd_value

5. Normalize the sign consistently.

Slopes like:

(-1, -1)

and

(1, 1)

represent the same direction.

We ensure consistency by forcing dx to be positive whenever possible. 6. Store the slope in the hash map.

The reduced pair (dy, dx) becomes the hash map key.

Each time we encounter the same slope again, we increment its frequency. 7. Track the largest line through the anchor.

The maximum frequency for a slope indicates how many points align with the anchor on the same line.

Since the anchor itself is not included in the count, the total number of points on that line is:

frequency + 1

8. Update the global maximum.

Repeat the process for every anchor point and keep the overall best result.

Why it works

A straight line is uniquely determined by a point and a slope. When we fix one anchor point, every point on the same line must produce the same slope relative to that anchor. By grouping points according to slope, we effectively group all collinear points together. Because every possible line must pass through at least one anchor point during the iteration, the algorithm eventually discovers the maximum collinear set.

Python Solution

from typing import List
from collections import defaultdict
from math import gcd

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        if n <= 2:
            return n

        max_points = 1

        for i in range(n):
            slopes = defaultdict(int)

            x1, y1 = points[i]

            current_max = 0

            for j in range(i + 1, n):
                x2, y2 = points[j]

                dx = x2 - x1
                dy = y2 - y1

                divisor = gcd(dx, dy)

                dx //= divisor
                dy //= divisor

                # Normalize sign
                if dx < 0:
                    dx *= -1
                    dy *= -1
                elif dx == 0:
                    dy = 1
                elif dy == 0:
                    dx = 1

                slope = (dy, dx)

                slopes[slope] += 1

                current_max = max(current_max, slopes[slope])

            max_points = max(max_points, current_max + 1)

        return max_points

The implementation begins by handling trivial cases where the number of points is at most two.

The outer loop selects each point as an anchor point. For every anchor, we create a fresh hash map that counts slope frequencies.

For every other point, we compute the directional vector (dy, dx). We then reduce the vector using gcd so mathematically equivalent slopes become identical hash map keys.

For example:

(2, 4) -> (1, 2)
(3, 6) -> (1, 2)

Both represent the same slope after reduction.

The normalization step ensures all equivalent slopes share exactly the same representation. This is especially important for vertical and horizontal lines.

The hash map tracks how many points share each slope. The largest slope frequency for the current anchor determines the largest line through that anchor.

Finally, we update the global maximum answer.

Go Solution

package main

func gcd(a, b int) int {
	if b == 0 {
		if a < 0 {
			return -a
		}
		return a
	}
	return gcd(b, a%b)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func maxPoints(points [][]int) int {
	n := len(points)

	if n <= 2 {
		return n
	}

	result := 1

	for i := 0; i < n; i++ {
		slopes := make(map[[2]int]int)

		x1, y1 := points[i][0], points[i][1]

		currentMax := 0

		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]

			dx := x2 - x1
			dy := y2 - y1

			divisor := gcd(dx, dy)

			dx /= divisor
			dy /= divisor

			// Normalize sign
			if dx < 0 {
				dx *= -1
				dy *= -1
			} else if dx == 0 {
				dy = 1
			} else if dy == 0 {
				dx = 1
			}

			slope := [2]int{dy, dx}

			slopes[slope]++

			currentMax = max(currentMax, slopes[slope])
		}

		result = max(result, currentMax+1)
	}

	return result
}

The Go solution follows the same algorithmic structure as the Python version. The main implementation difference is that Go does not support tuples as hash map keys, so we use a fixed-size array:

[2]int{dy, dx}

as the map key.

Go also requires explicit helper functions for gcd and max.

Because all coordinates fit comfortably inside standard integer ranges, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

[[1,1],[2,2],[3,3]]

Anchor Point (1,1)

Compared Point	dx	dy	Reduced Slope	Count
(2,2)	1	1	(1,1)	1
(3,3)	2	2	(1,1)	2

Current maximum line size:

2 + 1 = 3

Global answer becomes 3.

Anchor Point (2,2)

Compared Point	dx	dy	Reduced Slope	Count
(3,3)	1	1	(1,1)	1

Maximum line size from this anchor is 2.

Final answer:

3

Example 2

Input:

[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Anchor Point (1,1)

Compared Point	dx	dy	Reduced Slope
(3,2)	2	1	(1,2)
(5,3)	4	2	(1,2)
(4,1)	3	0	(0,1)
(2,3)	1	2	(2,1)
(1,4)	0	3	(1,0)

Slope counts:

Slope	Frequency
(1,2)	2
(0,1)	1
(2,1)	1
(1,0)	1

Maximum line size from this anchor:

2 + 1 = 3

Anchor Point (3,2)

Compared Point	Reduced Slope
(5,3)	(1,2)
(4,1)	(-1,1)
(2,3)	(-1,1)
(1,4)	(-1,1)

Slope (-1,1) appears three times.

Maximum line size:

3 + 1 = 4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each point computes slopes to every other point
Space	O(n)	Hash map stores slope frequencies for one anchor

The algorithm uses a nested loop over the points, giving O(n²) pair processing. Each slope computation and hash map operation runs in constant time. The hash map for slope counts can contain at most n - 1 entries for a single anchor point, so the auxiliary space complexity is O(n).

Test Cases

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        from collections import defaultdict
        from math import gcd

        n = len(points)

        if n <= 2:
            return n

        answer = 1

        for i in range(n):
            slopes = defaultdict(int)

            x1, y1 = points[i]

            current_max = 0

            for j in range(i + 1, n):
                x2, y2 = points[j]

                dx = x2 - x1
                dy = y2 - y1

                divisor = gcd(dx, dy)

                dx //= divisor
                dy //= divisor

                if dx < 0:
                    dx *= -1
                    dy *= -1
                elif dx == 0:
                    dy = 1
                elif dy == 0:
                    dx = 1

                slope = (dy, dx)

                slopes[slope] += 1

                current_max = max(current_max, slopes[slope])

            answer = max(answer, current_max + 1)

        return answer

solution = Solution()

assert solution.maxPoints([[1,1],[2,2],[3,3]]) == 3
# Basic diagonal line

assert solution.maxPoints([[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]) == 4
# Multiple possible lines

assert solution.maxPoints([[1,1]]) == 1
# Single point

assert solution.maxPoints([[1,1],[2,2]]) == 2
# Two points always form a line

assert solution.maxPoints([[1,1],[1,2],[1,3]]) == 3
# Vertical line

assert solution.maxPoints([[1,1],[2,1],[3,1],[4,1]]) == 4
# Horizontal line

assert solution.maxPoints([[0,0],[1,1],[-1,-1],[2,2]]) == 4
# Negative coordinates on same line

assert solution.maxPoints([[0,0],[2,4],[4,8],[1,2]]) == 4
# Slopes requiring GCD reduction

assert solution.maxPoints([[0,0],[1,2],[2,4],[3,1]]) == 3
# One outlier point

assert solution.maxPoints([[0,0],[94911151,94911150],[94911152,94911151]]) == 2
# Large coordinate values

Test	Why
[[1,1],[2,2],[3,3]]	Basic collinear diagonal
[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]	Multiple competing lines
[[1,1]]	Smallest possible input
[[1,1],[2,2]]	Two points always collinear
Vertical line case	Tests division-by-zero handling
Horizontal line case	Tests zero slope normalization
Negative coordinates	Ensures sign normalization works
GCD reduction case	Confirms equivalent slopes match
Outlier point case	Verifies largest line selection
Large coordinate values	Ensures arithmetic correctness

Edge Cases

Vertical Lines

Vertical lines are one of the most common sources of bugs because the slope formula involves division by dx. When dx = 0, floating point slope calculations would produce division-by-zero errors.

This implementation avoids division entirely. Instead, slopes are represented as reduced integer pairs (dy, dx). All vertical lines normalize to the same representation:

(1, 0)

This guarantees consistent hashing.

Equivalent Slopes With Different Representations

Different point pairs can produce mathematically identical slopes:

2/4
1/2
3/6

A naive implementation using raw (dy, dx) pairs would incorrectly treat these as different slopes.

The algorithm solves this by dividing both values by their greatest common divisor before storing them in the hash map.

Negative Direction Vectors

The same line can appear with opposite directional vectors:

(1,1)
(-1,-1)

Without normalization, these would become different hash map keys even though they represent the same slope.

The implementation fixes this by forcing dx to remain positive whenever possible. This ensures every slope has a unique canonical representation.