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.

- Save the line passing through the points

- If
- Return
`maxCount`

i`= count + duplicates`

.

- Initiate the maximum number of points on a line passing through the point
- Update the result
`max_count = max(max_count,`

`maxCount`

i)

- For each point

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 def add_line(i, j, count, duplicates): """ 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][0] y1 = points[i][1] x2 = points[j][0] y2 = points[j][1] # add a duplicate point 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(N^{2})

Please follow us on **Facebook**, **Twitter**. Also, read other interview questions** here**.