### silent__killer1's blog

By silent__killer1, history, 12 months ago, , 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… Comments (13)
 » 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.
 » 12 months ago, # | ← Rev. 2 →   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