Teaching Kids Programming – Max Number of Points on a Line

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers coordinates. Each list contains two integers [x, y] representing a point on the Cartesian plane. Return the maximum number of points that lie on some line.

Constraints
n ≤ 1,000 where n is the length of coordinates
Example 1
Input

coordinates = [
    [5, 1],
    [7, 2],
    [9, 3],
    [0, 0],
    [1, 1],
    [5, 5],
    [6, 6]
]

Output
4
Explanation
The points [[0, 0], [1, 1], [5, 5], [6, 6]] all fall in a line.

Max Number of Points on a Line

We need to bruteforce all pairs of points, and count the pair who has the same slope. If delta x is zero, i.e. horizontal line, the slope is infinity. Line equations are and we can compute k as delta y divided by delta x.

class Solution:
    def maxPointsOnLine(self, cords):
        n = len(cords)
        if n < 3:
            return n
        ans = 0
        for i in range(1, n):
            slopes = defaultdict(int)
            x1, y1 = cords[i]
            for j in range(i):
                x2, y2 = cords[j]
                s = (y2 - y1) / (x2 - x1) if x1 != x2 else math.inf
                slopes[s] += 1
            ans = max(ans, max(slopes.values()))
        return ans + 1

The time complexity is O(N^2) where N is the number of coordinates. The space complexity is O(N) – as we are using a hash table to store the unique slopes.

–EOF (The Ultimate Computing & Technology Blog) —