16.14. Best Line

Description

Given a two-dimensional graph with points on it, find a line which passes the most number of points.

Assume all the points that passed by the line are stored in list S sorted by their number. You need to return [S[0], S[1]], that is , two points that have smallest number. If there are more than one line that passes the most number of points, choose the one that has the smallest S[0]. If there are more that one line that has the same S[0], choose the one that has smallest S[1].

Example:


Input:  [[0,0],[1,1],[1,0],[2,0]]

Output:  [0,2]

Explanation:  The numbers of points passed by the line are [0,2,3].

Note:

2 <= len(Points) <= 300
len(Points[i]) = 2

Solutions

Solution 1: Brute Force

We can enumerate any two points $(x_1, y_1), (x_2, y_2)$, connect these two points into a line, and the number of points on this line is 2. Then we enumerate other points $(x_3, y_3)$, and determine whether they are on the same line. If they are, the number of points on the line increases by 1; otherwise, the number of points on the line remains the same. Find the maximum number of points on a line, and the corresponding smallest two point indices are the answer.

The time complexity is $O(n^3)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array points.

Python3JavaC++GoSwift

class Solution:
    def bestLine(self, points: List[List[int]]) -> List[int]:
        n = len(points)
        mx = 0
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                cnt = 2
                for k in range(j + 1, n):
                    x3, y3 = points[k]
                    a = (y2 - y1) * (x3 - x1)
                    b = (y3 - y1) * (x2 - x1)
                    cnt += a == b
                if mx < cnt:
                    mx = cnt
                    x, y = i, j
        return [x, y]