Question — You are given a array of 2d coordinates , you need to find out the maximum points lie on a line. where the array length is n<=100000 I am googling alot but i found the answer only when n<=1000 which will be done in o(n^2) . Can anyone share their approach for when n<=100000. Thankyou…

Sort 2d coordinates, and then find the maximum length of subarray with equal x or y coordinates.

That's not correct at all. If we have lines (1, 2) and (3, 4), your answer is one. However, there is a line passing through every two points.

Not always. For example, if n = 3 and points are (1,1),(2,2),(3,3). Correct answer is 3, your answer is 1

Yes, you are right. I did not understand the question correctly.

That smells like dp, huh?

See this blog (section "Radial sweep").

Is it just my bad or the radial sweep has complexity at least O(N^2) for this task?

Well, no, it is my bad for not reading the question completely :)

So is there any way to solve this problem??

Can you share link of the problem?

I dont have a particular problem type but I jus encountered with a question and what I think is this question can be solved down with this logic .Yes I have a photo of that question but not full image . I hope you will understand from the input test cases.

Problem image link -https://ibb.co/Y7mBv4H

If my logic is wrong then please tell me the correct approach for this problem.

Can you share link of problem? I doubt that it can be done faster than O(N^2) unless approx probabilistic methods are allowed?

I share the image of the above question which is not that particular question I am asking it is different but I think the logic will be the same.

Image link — https://ibb.co/Y7mBv4H