Solution Explanation for Max Points on a Line

This problem asks to find the maximum number of points that lie on the same straight line given a set of points in a 2D plane.

Approach 1: Brute Force

This approach checks every pair of points to determine the line they define, and then counts how many other points lie on that line. This is computationally expensive.

Time Complexity: O(n³), where n is the number of points. This is because we have three nested loops: the outer two loops iterate through all pairs of points (O(n²)), and the inner loop iterates through the remaining points to check collinearity (O(n)).

Space Complexity: O(1). We only use a few variables to store coordinates and counts.

Code (Python):

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        ans = 1
        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
                ans = max(ans, cnt)
        return ans

Approach 2: Slope Optimization

This approach is significantly more efficient. Instead of directly comparing points, we use the slope between pairs of points to identify points on the same line. Points (x1, y1) and (x2, y2) have the slope (y2-y1)/(x2-x1). If another point (x3, y3) is collinear, it will have the same slope when compared to (x1, y1) or (x2, y2). However, we need to handle vertical lines (infinite slope) and duplicate points carefully.

Time Complexity: O(n²), We iterate through pairs of points which is O(n²). The inner loop operations are all constant time.

Space Complexity: O(n), The hash map/dictionary used to store slopes can potentially store up to n entries in the worst case (all points lie on the same line).

Code (Python):

from collections import Counter
from math import gcd
 
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)
        n = len(points)
        max_points = 1
        for i in range(n):
            duplicates = 1
            slope_counts = Counter()  # Store slopes and their counts
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                if x2 == x1 and y2 == y1:
                    duplicates += 1
                    continue  # Skip duplicate points
                dx = x2 - x1
                dy = y2 - y1
                common_divisor = gcd(dx, dy)
                slope = (dx // common_divisor, dy // common_divisor)
                slope_counts[slope] += 1
            max_points = max(max_points, duplicates + max(slope_counts.values(), default=0))
 
        return max_points
 

The code uses Counter for efficient counting of slopes and gcd to normalize slopes. This avoids issues with floating-point comparisons. This refined approach provides a substantial improvement in efficiency compared to the brute force method. The handling of duplicate points is also crucial for correctness.