### 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) Take any point x and find the slope from x to every other point - O(n)

ReplyDelete2) 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)

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

ReplyDeleteInitialize 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)

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

Deletea line is defined by its equation ax+b = y;

ReplyDeleteInitialize 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)

Can we use something like this ?

ReplyDeleteSort the points based on x and y coordinates.

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