silent__killer1's blog

By silent__killer1, history, 5 months ago, In English,

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…

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

That smells like dp, huh?

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

See this blog (section "Radial sweep").

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share link of the problem?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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