Max Points on a Line - How to start

This is one of the problems @yuzhoujr recommended me in an email, except I actually don’t know how to start out with this problem.

Does anyone have an idea?

EDIT: I forgot the link. https://leetcode.com/problems/max-points-on-a-line/

1 Like

I would start by identifying general ways to uniquely identify a line. :link:

A line can be uniquely identified using it’s slope :mountain:, and a point on the line :green_circle: . Using this information, we should be able to store lines already encountered and keep track :railway_track: of the number of points on each line, and finally return the max points on a line. :trophy:

Problem is, with an initial approach like this, there are (n-1)! possibilities of lines. With each pair, I have to calculate not only the slope, but also the y-intercept, and iterate through the remaining n - 2 points to see which ones would x_point * slope equal y_point. That’s another factor of n.

With this, the runtime complexity would be O((n - 1)! * n) = O(n!). That’s quite ridiculous.

The question is very ambiguous because we don’t know what the maximum size of the points array is; all we know is that it has two columns: one for x, and one for y.

You need to compare every point with the remaining points. That’s O(n^2) complexity. I don’t quite see how you got the (n-1)! possibilities.

Yes, it’s my fault. I wasn’t thinking correctly. It’s O(n^2).

Because I’m testing my line with all of the points to find out which ones match the y value on calculation, my brute force approach is O(n^3) in runtime.