### 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?

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)

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)

1. Your complexity analysis assumes that HashMap could be updated in O(1). So, overall complexity should be expected O(n*n).

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)

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