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

1
2
3
4
5
6
7
8
9
coordinates = [
    [5, 1],
    [7, 2],
    [9, 3],
    [0, 0],
    [1, 1],
    [5, 5],
    [6, 6]
]
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 tex_8ae744ec443ce21386b00c105e912219 Teaching Kids Programming - Max Number of Points on a Line algorithms math python teaching kids programming youtube video and we can compute k as delta y divided by delta x.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
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) —

GD Star Rating
loading...
386 words
Last Post: The Java Method to Read Content of File into a String
Next Post: Input Password Function in Console Using Java

The Permanent URL is: Teaching Kids Programming – Max Number of Points on a Line

Leave a Reply