# 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 same straight Line.

### Example:

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

Output: 3

## Solution:

Algorithm

Let’s discuss the algorithm which will be used in this 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)
{"ft_lang_label":"__label__en","ft_lang_prob":0.7360925,"math_prob":0.99731,"size":3553,"snap":"2021-43-2021-49","text_gpt3_token_len":964,"char_repetition_ratio":0.17976895,"word_repetition_ratio":0.06392694,"special_character_ratio":0.2938362,"punctuation_ratio":0.14772727,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9985761,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-27T10:57:30Z\",\"WARC-Record-ID\":\"<urn:uuid:c99b5739-5e59-402b-b0bf-031656841386>\",\"Content-Length\":\"100568\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a0b31e4f-7e4f-48d9-b09c-6bfe30bd71d1>\",\"WARC-Concurrent-To\":\"<urn:uuid:ef1eeef7-fd25-48a2-804a-b5d2f6a25ceb>\",\"WARC-IP-Address\":\"104.21.40.253\",\"WARC-Target-URI\":\"https://coduber.com/max-points-on-a-line-from-given-points/\",\"WARC-Payload-Digest\":\"sha1:2ZDTQ272VODU6WHXOCKXCOJEPI6U63T2\",\"WARC-Block-Digest\":\"sha1:QGSUBEFFDMBPV2AM64RKBFHVNLAKSENZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323588113.25_warc_CC-MAIN-20211027084718-20211027114718-00655.warc.gz\"}"}