Maximum Points On Straight Line

Hard
0/120
Average time to solve is 10m
30 upvotes
Asked in companies
UberAdobeApple

Problem statement

You are given a 2-D plane, and some 'N' integer coordinates in the form of (X, Y), where 'X' is the x-coordinate and 'Y' is the y-coordinate, all of which lie on that plane. You need to find the maximum number of coordinates among these which can form a straight line.

Note: 
1. All the coordinates are integer coordinates.
2. There can be two identical coordinates.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T', denoting the number of test cases.

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

The next N lines of each test case contain 2 space-separated integers which represent the coordinates of a given point.
Output Format: 
For each test case, every line of output prints the maximum number of points which lie on a straight line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <=  50
1 <= N <= 10^3
-10^4 <= X, Y <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
2
1 1
5 5
6
-1 -1
0 0
1 1
2 2
3 3
3 4
Sample Output 1:
2
5
Explanation For Sample Output 1:
For the first test case, since there are only two points, they can always form  a straight line.

For the second test case, look at the picture below.


We can easily see that 5 out of 6 points lie on a straight line. Hence 5 is the answer.
Hint

Try to develop the algorithm step by step.

Approaches (1)
Implementation

 Algorithm:

 

  1. Since this is a problem with coordinates and straight lines, we can use the concept of slope of the line to find the answer.
  2. The main idea is to find the slope of one point with all the other points and then find which of these points have the same slope and lie on the same line.
  3. Let the 2D vector ‘POINTS[N][2]’ represent the coordinates of the points that we have.
  4. For each of the coordinates from ‘i’ = 0 to ‘N’ - 1 we can do the following:
    • Create a map<double, int> where the key of the map is the slope and the value for each slope will store the number of points with the same slope with the given point.
    • Let SAMEPOINT = 0 represent the same overlapped point if there is any overlapped point.
    • Let SAMEX = 0 represent the set of coordinates that have the same X coordinates.
    • Now for all the points from ‘j’ = 0 to ‘j’ = ‘N’ - 1 do the following:
      • If ‘POINTS[j][0] = ‘POINTS[i][0] and ‘POINTS[j][1] = ‘POINTS[i][1], that means both the points are same, so increment samePoint by 1, i.e. SAMEPOINT = SAMEPOINT += 1.
      • If ‘POINTS[j][0] = ‘POINTS[i][0], then the coordinates have same X coordinates, so increment SAMEX by 1.
      • The slope for each of the set of two points will be slope =  (double) (‘POINTS[j][1] - ‘POINTS[i][1]) / (double) (‘POINTS[j][0] - ‘POINTS[i][0]);
      • Now if the slope was not present in the map then we can hash the slope into the map and keep the count as 2.
      • Else we can just increment the count of the slope by 1.
    • After exiting from the inner loop we can just iterate through the values of the map and find the maximum frequency and keep on updating the answer.
  5. After the end of this loop we will have the answer.
Time Complexity

O(N^2), where N is the number of coordinates.

 

For each ‘i’ from 0 to N - 1 we are iterating for N times.  Thus our total number of iterations will be N * N. Hence our time complexity will be O(N^2).

Space Complexity

O(N^2), where N is the number of coordinates.

 

Because max number of slopes possible are N * N and so, HashMap may have total N * N values in it. Hence our space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Maximum Points On Straight Line
Full screen
Console