Skip to main content

149. Max Points on a Line

https://leetcode.com/problems/max-points-on-a-line/description/

Python​

Slopes as Hash Key​

  • Time: O(NlogN)
  • Space: O(N)
from collections import defaultdict


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) < 2:
            return 1

        ans = 0
        for i in range(len(points)-1):
            mapper = defaultdict(int)
            for j in range(i+1, len(points)):
                point1 = points[i]
                point2 = points[j]

                # Case of vertical line
                if point1[0] == point2[0]:
                    mapper["v"] += 1
                    continue

                # Case of others
                slope = (point1[1]-point2[1]) / (point1[0]-point2[0])
                mapper[slope] += 1

            # print("From", points[i], ", the points with same slope", mapper)

            ans = max(ans, max(mapper.values())+1 )
        return ans