Q) Given a 2D array of size n that represents the x and y coordinates([x,y]), find the number of collinear triplets.If collinear triplets>1e9, then return -1.
N<=1000
----------------------------------------------- This question came in yesterday's Microsoft OA. I was not able to come up with an efficient solution and ultimately wrote an O(n^3) solution using the idea that the area of triangle formed by three collinear points is 0.
Please suggest an efficient solution.
here is a general idea
for each point(call it pi), traverse other points, calculate slope and numbers of each slope, store in a (hash)map. something like map<pair<int, int>, int>.
then for a desired triplet, we assume pi is fixed, and for every pair(slope and count) in map, we can add all $$$\binom{count}{2} $$$ to the answer.
for some implement detail, maybe you'd better sort the point first, and take care of computing slope
The Problem here is its difficult to create map for slopes since slopes are double valued, so can't be used as keys. So for that create a structure, that stores them in pair format preferably({num, den}), by dividing both num and den by their gcd.
Basically for every point you have a map that has {slope, cnt}. As stated add C(cnt, 2) to the answer, and the final answer will be ans/3, as every triplet is being counted thrice.
Also take care of the case when num/den becomes 0 in slope, in that case store intercepts correctly.
yes of course we won't store slope as floating point, that's why i say "map<pair<int, int>, int>" . sorry for other parts, maybe a bit of misleading.