Max Points on a Line

HardMathslope hashing

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array points where points[i] = [xi, yi] is the location of the i-th point on a 2D plane. A point may appear more than once in the array (two entries can share the exact same coordinates). Return the maximum number of points that all lie on a single straight line. A line is defined by any two distinct positions, and a point "lies on" that line if it falls exactly on it. Note that duplicated points stacked on the same coordinate always count together, since any line through that coordinate passes through all of them. The challenge is to count collinear points without ever computing a floating-point slope, which can introduce rounding errors. Instead, represent each line direction exactly using integer arithmetic.

Examples

Input: points = [[1,1],[2,2],[3,3]]
Output: 3
All three points sit on the line `y = x`, so the maximum is 3.
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
The points `[1,1]`, `[3,2]`, `[5,3]` lie on the line of slope `1/2`; adding `[1,4]`... actually the best line passes through 4 of the points. No line contains more than 4 of them.
Input: points = [[0,0],[0,1],[0,2],[1,5]]
Output: 3
The first three points share the vertical line `x = 0`. Vertical lines have an undefined float slope, which is why an exact integer representation is needed.

Constraints

  • `1 <= points.length <= 300`
  • `points[i].length == 2`
  • `-10^4 <= xi, yi <= 10^4`
  • All points are given as integer coordinates.
  • The input may contain duplicate points (same coordinate listed multiple times).

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.