Python solution with detailed explanation


  • 0
    G

    Solution with discussion https://discuss.leetcode.com/topic/75076/python-solution-with-detailed-explanation

    Max Points on a Line https://leetcode.com/problems/max-points-on-a-line/

    Test all pairs: O(N^2)

    • There can be duplicate points in the list. Dedupe and keep a count of frequency.
    • Test every pair and compute the line implied by it. A line is defined by a slope and intercept. But we can avoid maintaining intercept since we can fix a point A, and find all lines from A i.e. AB, AC.
    • To compute the slope, use the Fraction class which allows us to define slope as a ratio of numerator and denominator. This class makes sure 6/2 is stored 3/1.
    # Definition for a point.
    # class Point(object):
    #     def __init__(self, a=0, b=0):
    #         self.x = a
    #         self.y = b
    from fractions import Fraction
    from collections import defaultdict
    
    class Line(object):
        def __init__(self, p1x, p1y, p2x, p2y):
            m_num, m_den = p2y - p1y, p2x - p1x
            if m_den != 0:
                f = Fraction(m_num, m_den)
                self.slope_key = (f.numerator, f.denominator)
            else:
                self.slope_key = "INF"
            return
    
    class Solution(object):
        def dedupe_points(self, points):
            pts_freq = defaultdict(int)
            for p in points:
                pts_freq[(p.x, p.y)] = pts_freq[(p.x, p.y)] + 1
            return pts_freq
        
        def maxPoints(self, points):
            """
            :type points: List[Point]
            :rtype: int
            """
            pts_freq = self.dedupe_points(points)
            points = [k for k in pts_freq]    
            if len(points) == 1:
                return pts_freq[points[0]]
            max_so_far, N = 0, len(points)
            for i in range(N):
                lines_from_i = {}
                for j in range(i+1,N):
                    p1, p2 = points[i], points[j]
                    line_slope = Line(p1[0], p1[1], p2[0], p2[1]).slope_key
                    lines_from_i.setdefault(line_slope, pts_freq[p1])
                    lines_from_i[line_slope] = lines_from_i[line_slope] + pts_freq[p2]
                    max_so_far = max(max_so_far, lines_from_i[line_slope])
            return max_so_far
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.