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 maxCounti 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


            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²)

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