silent__killer1's blog

Max points on a line
By silent__killer1, history, 6 years 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

Comments Comments (7)
| Write comment?
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

See this blog (section "Radial sweep").

→ Reply
  • »
    »
    6 years 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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years 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?

→ Reply