Shortest C++ solution I come up with

interview-questions
google
Tags: #<Tag:0x00007f2426e8e238> #<Tag:0x00007f2426e8dfe0>

#1

24%20PM


#2

Don’t we need to map pair of slope and INTERCEPT instead of mapping only slope with number of points -OR- INTERCEPT is redundant ? I mapped the pair as I mentioned above and code got accepted.


#3

Yours is a better way, O(n). I just did lazy O(n²).

upd: both will be O(n²).


#4

how is it O(n)? can you provide with code


#5

My bad it will also be O(n²).


#6

Your code is wrong!
It is only working because the test cases are weak.
It won’t work for this test case - 6 1 1 1 1 2 2 3 3 2 2 3 3, the answer should be 6 while your code returns it as 5


#7

My assumption was that all n points will have different coordinates. If you want to solve for redundant points you can store frequency and add to the answer.
maxpoints = max(maxpoints, points[slope]+freq[{A[i], B[i]}]);