Max points on the straight line
Difficulty: Hard
Asked in: Amazon, Google
Understanding the Problem
Problem Description
Given N point on a 2D plane as pair of (x, y) coordinates, Write a program to find the maximum number of point which lie on the same line.
Example 1
Input: A[][] = [[1,1],[2,2],[1,2],[3,3],[2,3]]
Output: 3
Explanation: The maximum number of point which lie on same line are 3, those points are [1,1], [2, 2] and [3, 3]
Example 2
Input: A[][] = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation: The maximum number of point which lie on same line are 4, those points are [3,2], [4,1], [2,3] and [1, 4].
Solutions
We will be discussing two different ways to solve this problem
 Brute Force — For every pair of points, check how many other points are collinear with them and maintain track of it.

Using Map
— For every point, maintain a hashmap for the slope of that point to every other point, and maintain the
max_pts
count.
You may try this problem here .
1. Brute Force
To compute the number of points on a line, we need to
 We need to take two points and check if all other points are collinear with those two points.
 We need to keep track of the number of points that are collinear with the two points as we have been asked the maximum number of points lying on a straight line.
 We also need to keep in mind the case when two points could coincide. If the two points coincide, then there could be many lines based on two coinciding points.
Solution Steps
 For every pair of noncoinciding points, check how many other points are collinear with those two points.

Maintain a
max_pts
that will store the maximum number of points that will be lying on the same line.
Pseudo Code
// check whether the three points are on the same line
int coline(int[] a,int[] b,int[] c){
if (a[0]c[0])*(b[1]c[1]) == (a[1]c[1])*(b[0]c[0])
return 1
else
return 0
}
int maxPoints(int[][] points) {
int n = points.size()
int max_pts = 0
for(int i = 0 to i < n){
for(int j = i+1 to j < n){
if(points[i][0]==points[j][0] && points[i][1]==points[j][1])
continue
int sum = 0
for(int k = 0 to k < n)
sum += coline(points[i],points[j],points[k])
max_pts = max(max_pts,sum)
}
}
if(max_pts==0)
return n
else
return max_pts
}
Complexity Analysis
Time Complexity: O(n³)
Space Complexity: O(1)
Critical Ideas to Think
 We took two points and calculated its slope and then look for every other point with the same slope and thus maintained the counter. But a unique line is determined both by the slope and intercept. How did we manage to maintain a counter for each slope without checking for intercept?
 How did we ensure that this solution is correct even for overlapping points?
 What does coline function represent?
2. Using Map
A line passing through two points has a unique slope. One could deduce that if we take a point
p1
from the set of points and draw lines from
p1
to all other points, then each of them will give a slope and if there are same slopes for multiple points, then definitely, the points with the same slope will be on the same line or you can say collinear. So, if you will think about it, when we pick points one by one from the set of points and find slopes for every other point, we removed the possibility of parallel lines for each iteration. Thus, maintaining a hash map of slope will help us identify the maximum number of points lying on the same line.
Solution Steps
 For each point, find the slope from that point to every other point.
 Create an orderedmap and store the total number of collinear points against the slope.

To find the slope, use the formula
(x2 — x1) / (y2 — y1)
. Usedouble
instead offloat
to maintain the precision level. 
To manage the edge cases, Create an
overlap
variable to check for repeating points and create avertical
variable to count the number of points lying on the line parallel to the Yaxis. 
Lastly, maintain a
res
to store the maximum number of points lying on the same line.
Pseudo Code
int maxPoints(int[][] points) {
int max_pts = 0
for (int i = 0 to i < points.size()) {
int localmax = 0, overlap = 1, vertical = 1;
map<double, int> m
for (int j = i + 1 to j < points.size()) {
if (points[i][0] == points[j][0] && points[i][1] == points[j][1])
overlap = overlap + 1
else
if (points[i][0] == points[j][0])
vertical = vertical + 1
else {
slope = double(points[i][1]  points[j][1]) / (points[i][0]  points[j][0])
m[slope] = m[slope] + 1
}
}
for (slope in m)
localmax = max(m[slope], localmax)
max_pts = max(vertical, max(localmax + overlap, max_pts))
}
return max_pts
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n)
Critical Ideas to Think
 Why did we create a map to store the slope for each point?
 How did we maintain the precision of slope for large numbers?
 How did we manage for infinity slope and overlapping points in the above approach?

We took a point
A
and tried to find the slope for the lines starting fromA
to every other pointB
and stored into a map. A unique line is determined both by the slope and intercept. How did we manage to maintain a counter for each slope without checking for intercept?
Comparison of Different Solutions
Suggested Problems to Solve
 Program to find line passing through 2 Points
 Find points at a given distance on a line of a given slope
 Check whether a straight line can be formed using N coordinate points
 Number of ordered points pair satisfying line equation
 Number of horizontal or vertical line segments to connect 3 points
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding!
Enjoy Algorithms!