Best Line

Easy
0/40
Average time to solve is 20m
profile
Contributed by
3 upvotes
Asked in company
Intuit

Problem statement

You are given an array ARR of N points in a 2-Dimensional grid. Your task is to find the maximum number of collinear points in the grid.

It is guaranteed that all the points in ARR are pairwise distinct.

For example:

ARR = [ (2,4), (4,8), (-1,2), (1,2) ]
Here answer is 3 as (1,2), (2,4), (4,8) lie on the same line.

Image

Note: Three points A, B, C are collinear if there exists a line that passes through all of them.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains an integer 'N', the number of points in ARR.

The next 'N' lines of each test case contain two space-separated integers ‘X’ and ‘Y’ denoting the coordinates of the points in ARR.
Output Format: 
For each test case print an integer denoting the maximum number of collinear points.  

Output for each test case will be printed in a separate line.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 2000
-10^9 <= X[i], Y[i] <= 10^9

All the points in ARR are pairwise distinct.

Time Limit: 1 sec
Sample Input 1:
2
2
1 2
1 1
4
0 2
0 6
0 -2
0 0
Sample Output 1:
2
4
Explanation For Sample Input 1:
For the first test case, two points are always collinear.

image 

For the second test case, all four points lie on Y-axis.

image

Sample Input 2:
2
1
0 0
6
-6 2
-2 -2
2 -6
6 -10
-4 4
0 8
Sample Output 2:
1
4
Explanation For Sample Input 2:
For the first test case, there is only one point given. So, answer is 1.

For the second test case, max four points lie on a same line.
Hint

After fixing a single point on line all the other collinear points makes the same angle with the fixed point and X-axis.

Approaches (1)
Slope Point Form Approach

Approach: The key observation here is that if we will fix two points on a line all other points which are collinear can be uniquely determined. We will fix a certain point and then for all the other points, we can make a counter based on the slope of the segment joining it and the fixed point.

 

The Algorithm will be:

 

  1. We will store the final result in 'ANS' initialized to 1.
  2. We will iterate over all the points in ‘ARR’.
    • Fix this point on the line.
    • Creating a counter ‘CNT’ using hashmap, to store the number of points with the same slope.
    • We will now iterate over all points other than the point we have fixed-
      • Calculate the slope of the segment joining it and the fixed point.
      • Increment the ‘CNT’ of the slope.
    • Ans is the maximum of itself and the max value of ‘CNT’.
  3. Finally, return ‘ANS’.
Time Complexity

O(N^2 * logN), where N is the size of the array/list ARR.

 

Since for every point we are iterating over all other points the time complexity will be O(N^2) and Log(N) is for map lookups.

Space Complexity

O(N), where N is the size of the array/list ARR.

 

All the points can have a different angle with a fixed point, so we have to store the counter for at max N elements.

Code Solution
(100% EXP penalty)
Best Line
Full screen
Console