149. Max Points on a Line

Problem¶

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

Input: points = [[1,1],[2,2],[3,3|1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4|1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -10**4 <= x_i, y_i <= 10**4
• All the points are unique.

Solve¶

White board¶

• Let call the total input = n = points.length
  • Every possible two point is: 300 x (300-1) = n ** 2 ~ 90000 ~ 10 ** 6
  • For normal calculation, I don’t want my theoretical calculation complexity (time complexity) > 25_000_000, which mean we have about 25 ~ log(n) ~ log(n ** 2) nested loop to solve the problem if we try doing this path.

Attempt flow chart (I think I need to use draw.io, paint is pain)

Ignore float point.¶

This is a wrong answer, but non the less, I try it anyway

We base on 2 function

• Vector
• Normalized