# Max Points on a Line From Given Points

This is a very common interview question asked on Facebook, Google, Microsoft, etc. Let’s get into the question first and then we can see the solutions of the problem Max Points on a Line.

## Question:

Given n number of points on a 2D plane, find the maximum number of points in that which will lie in the same straight line.

### Example:

Input: [[1,1], [2,2], [3,3]]

Output: 3

## Solution (Python):

Algorithm

Let’s discuss the algorithm which will be used in these coding questions.

• Initiate the maximum number of points `maxCount = 1`.
• Iterate over all points `i` from `0` to `K - 2`.
• For each point `i` find a maximum number of points `maxCount`i on a line passing through the point `i` :
• Initiate the maximum number of points on a line passing through the point `i` : `count = 1`.
• Iterate over next points `j` from `i + 1` to `N - 1`.
• If `j` is a duplicate of `i`, update a number of duplicates for point `i`.
• If not:
• Save the line passing through the points `i` and `j`.
• Update `count` at each step.
• Return `maxCounti` `= count + duplicates`.
• Update the result `max_count = max(max_count, maxCounti)`
```class Solution(object):
def maxPoints(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
def max_points_in_a_line(i):
"""
Compute the max number of points
for a line containing point i.
"""
def slope_coprime(x1, y1, x2, y2):
""" to avoid the precision issue with the float/double number,
using a pair of co-prime numbers to represent the slope.
"""
deltaX, deltaY = x1 - x2, y1 - y2
if deltaX == 0:    # vertical line
return (0, 0)
elif deltaY == 0:  # horizontal line
return (sys.maxsize, sys.maxsize)
elif deltaX < 0:
# to have a consistent representation,
#   keep the delta_x always positive.
deltaX, deltaY = - deltaX, - deltaY
gcd = math.gcd(deltaX, deltaY)
slope = (deltaX / gcd, deltaY / gcd)
return slope

"""
Add a line passing through i and j points.
Update max number of points on a line containing point i.
Update a number of duplicates of i point.
"""
# rewrite points as coordinates
x1 = points[i]
y1 = points[i]
x2 = points[j]
y2 = points[j]
if x1 == x2 and y1 == y2:
duplicates += 1
# add a horisontal line : y = const
elif y1 == y2:
nonlocal horizontal_lines
horizontal_lines += 1
count = max(horizontal_lines, count)
# add a line : x = slope * y + c
# only slope is needed for a hash-map
# since we always start from the same point
else:
slope = slope_coprime(x1, y1, x2, y2)
lines[slope] = lines.get(slope, 1) + 1
count = max(lines[slope], count)
return count, duplicates

# init lines passing through point i
lines, horizontal_lines = {}, 1
# One starts with just one point on a line : point i.
count = 1
# There is no duplicates of a point i so far.
duplicates = 0
# Compute lines passing through point i (fixed)
# and point j (interation).
# Update in a loop the number of points on a line
# and the number of duplicates of point i.
for j in range(i + 1, n):
count, duplicates = add_line(i, j, count, duplicates)
return count + duplicates

# If the number of points is less than 3
# they are all on the same line.
n = len(points)
if n < 3:
return n

maxCount = 1
# Compute in a loop a max number of points
# on a line containing point i.
for i in range(n - 1):
maxCount = max(max_points_in_a_line(i), maxCount)
return maxCount```

Complexity Analysis

• Time complexity: O(N2)