LeetCode Top Interview 150

149. Max Points on a Line

Hard

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

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

Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

Output: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solution

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        result = min(len(points), 2)
        n = len(points)
        for i in range(n):
            hashmap = {}
            for j in range(n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x2 - x1 == 0:
                    m = float("inf")
                else:
                    m = (y2 - y1) / (x2 - x1)
                if m in hashmap:
                    hashmap[m].add(i)
                    hashmap[m].add(j)
                else:
                    hashmap[m] = set([i, j])                
                result = max(len(hashmap[m]), result)
        
        return result

This site is open source. Improve this page.