Max Points on a Line

Max Points on a Line

What is this problem about?

The Max Points on a Line problem gives you an array of 2D coordinates representing points on an X-Y plane. Your objective is to find the maximum number of points that lie on the exact same straight line. A line can be horizontal, vertical, or diagonal.

Why is this asked in interviews?

This is a Hard-level geometry and Hash Map problem. Interviewers love it because it forces candidates to deal with floating-point precision issues and edge cases. Calculating slopes using standard division ($y / x$) leads to rounding errors that break equality checks. It evaluates a candidate's ability to use Greatest Common Divisor (GCD) to represent slopes as irreducible fractions.

Algorithmic pattern used

This problem leverages Hash Maps and Geometry (Slope Calculation). For every point A in the array:

1. Create a local Hash Map to track the frequency of slopes connecting A to all other points B.
2. The slope between A and B is defined by dy = B.y - A.y and dx = B.x - A.x.
3. To avoid precision loss from floats, calculate gcd(dy, dx). Divide both dy and dx by their GCD to reduce the fraction to its simplest form (e.g., 2/4 becomes 1/2).
4. Use the string or tuple "dy/dx" as the key in the Hash Map. Track the maximum frequency.
5. The maximum points on a line passing through A is max_frequency + 1 (to include A itself).

Example explanation

Points: (1,1), (2,2), (3,3), (1,4) Let's anchor on A = (1,1).

• Point B = (2,2): dx = 1, dy = 1. gcd(1,1) = 1. Key: "1/1". Map: {"1/1": 1}.
• Point C = (3,3): dx = 2, dy = 2. gcd(2,2) = 2. dy/gcd = 1, dx/gcd = 1. Key "1/1". Map: {"1/1": 2}.
• Point D = (1,4): dx = 0, dy = 3. gcd(3,0) = 3. dy/gcd = 1, dx/gcd = 0. Key "1/0". Map: {"1/1": 2, "1/0": 1}. The highest count is 2 (from "1/1"). Adding the anchor point A gives $2 + 1 = 3$ points on that specific line. We repeat this anchoring on all other points to find the global maximum.

Common mistakes candidates make

The most fatal mistake is calculating the slope as a double or float (e.g., double slope = (double)dy / dx;). Floating-point arithmetic is inherently imprecise; two points that are very close to being on the same line might evaluate as equal, or vice versa. Another mistake is improperly handling vertical lines (where dx == 0), which causes a divide-by-zero exception if not using the GCD fraction format.

Interview preparation tip

To master the Max Points on a Line interview pattern, you must memorize the Euclidean algorithm for calculating the Greatest Common Divisor (GCD): int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } This tiny, 1-line function is the absolute secret to solving slope-based geometry problems safely and accurately.