Maximum Number of Collinear Points

Source: Asked to me by a friend - who was asked this question in an interview at Facebook

Problem:

Given n points on a 2D plane, find the equation of the line with maximum number of collinear points. What is the time complexity of your algorithm?






Comments

  1. 1) Take any point x and find the slope from x to every other point - O(n)
    2) Find the number of points for each slope by hashing or building a binary search tree - O(nlogn)
    3) Find the max number of point for any slope
    4) Repeat this for every point and find the max among them

    Total time complexity - O(n*n*logn)

    ReplyDelete
  2. a line is defined by the equation ax+b = y;

    Initialize a hashmap with key (a,b) and an integer value;

    for each edge of two points :
    compute a,b and increment the integer value associated with (a,b) in the hashmap
    O(n*n)

    compute max of the values in the hashmap and return key associated
    O(n*n)

    Total time complexity O(n*n)

    ReplyDelete
  3. a line is defined by its equation ax+b = y;

    Initialize a hashmap with key (a, b) and integer value

    for each edge of two points, compute a and b,
    increment the value associated with key (a,b)
    O(n*n)

    compute the max of values in the hashmap and return key associated
    O(n*n)

    Total time complexity : O(n*n)

    ReplyDelete
  4. Can we use something like this ?

    Sort the points based on x and y coordinates.

    Then basically use DP approach to get the longest increasing sequence with the same slope

    ReplyDelete

Post a Comment