dsa · hard
Flying in Formation
A radar sweep records points, a list of [x, y] positions (integers, duplicates allowed — two records at the same spot are two aircraft in formation). Return the largest number of records that lie on one straight line. Two or more records are always on some line together, so with at least one record the answer is at least 1.
Arguments
points— the radar records, each[x, y]integer coordinates
Example
points = [[1,1],[2,2],[3,3]]
All three lie on the diagonal y = x → 3.
points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] → the line of slope -1 through [1,4], [2,3], [3,2], and [4,1] holds four; no line holds five → 4.
Constraints
0 <= points.length <= 300 -10^4 <= points[i][0], points[i][1] <= 10^4 all coordinates are integers Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [[1,1],[2,2],[3,3]] Expected: 3
Example 2
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Expected: 4
Example 3
Input: [[0,0]] Expected: 1