149.Max_Points_on_a_Line(Hard).md

149. Max Points on a Line (Hard)

Date and Time: Feb 9, 2025, 11:05 (EST)

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

Question:

Given an array of points where points[i] = [x_i, y_i] 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

• -10^4 <= x_i, y_i <= 10^4

• All the points are unique.

Walk-through:

1. Use dictionary to save points with the same line. We can do it by calculating the slopes of each point with other points, use the slope as key, and update the counts {slope: counts}. For each point, we need to create a new dictionary.

2. Return the maximum counts. Everytime after we update counts of a slope, we update ans = max(ans, slopes[slope]).

Python Solution:

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        # For each pt, find the slope of other pts, save slope with counts, return the max
        
        # TC: O(n^2), n=len(points), SC: O(n)
        ans = 0
        # Compare each pt with other pts to find slope
        for i in range(len(points)):
            slopes = collections.defaultdict(int)      # new slope map for each pt, {slope: counts}
            for j in range(i+1, len(points)):
                # Calculate slope by two pts
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x2-x1 == 0:
                    slope = float("inf")
                else:
                    slope = (y2-y1) / (x2-x1)
                slopes[slope] += 1
                ans = max(ans, slopes[slope])
        return ans + 1

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$