How do you solve Max Points on a Line on LeetCode?

Max Points on a Line (LeetCode #149) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding slopes is crucial for determining collinearity.

What is the brute force solution for Max Points on a Line?

The brute force approach for Max Points on a Line is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every pair of points to determine how many other points lie on the same line defined by those two points. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Max Points on a Line?

Max Points on a Line uses the following concepts: Array, Hash Table, Math, Geometry. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Max Points on a Line?

Explain your thought process clearly. Discuss edge cases, like vertical lines. Be prepared to optimize your solution if asked.

What are common mistakes when solving Max Points on a Line?

Not normalizing slopes, leading to incorrect counts. Forgetting to handle vertical lines separately.

#149

Max Points on a Line

Hard

ArrayHash TableMathGeometryHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution uses a hash map to count slopes efficiently, allowing us to determine the maximum number of points on a line in linear time relative to the number of points.

⚙️

Algorithm

4 steps

1Step 1: Initialize a variable to keep track of the maximum points found.
2Step 2: For each point, calculate the slope to every other point using a hash map to count occurrences of each slope.
3Step 3: Normalize slopes to avoid precision issues and handle vertical lines.
4Step 4: Update the maximum points based on the highest count of slopes.

solution.py24 lines

1# Full working Python code
2from collections import defaultdict
3
4def maxPoints(points):
5    if len(points) < 2:
6        return len(points)
7    max_points = 0
8    for i in range(len(points)):
9        slopes = defaultdict(int)
10        for j in range(len(points)):
11            if i != j:
12                dx = points[j][0] - points[i][0]
13                dy = points[j][1] - points[i][1]
14                gcd = get_gcd(dy, dx)
15                slope = (dy // gcd, dx // gcd)
16                slopes[slope] += 1
17        max_points = max(max_points, max(slopes.values(), default=0) + 1)
18    return max_points
19
20def get_gcd(a, b):
21    while b:
22        a, b = b, a % b
23    return a
24

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops, but we use O(n) space for the hash map to store slopes, which allows us to efficiently count points on the same line.

1Understanding slopes is crucial for determining collinearity.
2Normalization of slopes helps avoid precision issues.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.