LeetCode Solutions Blog

Max Points on a Line

Number: 149

Difficulty: Hard

Paid? No

Problem Description

Given an array of points where each point is represented as [x, y], find the maximum number of points that lie on a single straight line.

Key Insights

Use a nested loop to treat each point as an anchor and calculate slopes to all other points.
Represent slopes as a reduced fraction (dy/dx) using the greatest common divisor (gcd) to avoid floating-point imprecision.
Specially handle vertical lines (when dx is 0) by using a unique identifier.
The problem naturally leads to an O(n²) solution by processing each pair of points.
Use a hash table (or dictionary) to count how many points form the same slope with the anchor point.

Space and Time Complexity

Time Complexity: O(n²) where n is the number of points, since every pair of points is compared. Space Complexity: O(n) for the hash table used for storing slope counts for each anchor point.

Solution

The solution iterates through each point and treats it as an anchor. For every other point, we calculate the slope between the anchor and that point. The slope is computed as a pair (dy, dx) reduced to its simplest form via gcd. For vertical lines (dx == 0), we use a special key. A hash table is used to count occurrences of each slope. The maximum number of points with the same slope (plus the anchor) is recorded. The final result is the maximum count from all anchors.

Code Solutions

import math
from collections import defaultdict

class Solution:
    def maxPoints(self, points):
        # If there are less than 3 points, return the count directly
        if len(points) < 3:
            return len(points)
        
        max_points = 0

        # Iterate over each point treating it as an anchor
        for i in range(len(points)):
            slopes = defaultdict(int)
            same = 1  # Count the anchor point itself
            curr_max = 0

            # Compare with every other point after i
            for j in range(i + 1, len(points)):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]

                # Deal with the (theoretical) duplicate point case.
                if dx == 0 and dy == 0:
                    same += 1
                else:
                    # Handle vertical lines
                    if dx == 0:
                        slope = ('inf', 0)
                    else:
                        gcd = math.gcd(dx, dy)
                        dx_norm = dx // gcd
                        dy_norm = dy // gcd
                        # Normalize representation: ensure dx_norm is positive
                        if dx_norm < 0:
                            dx_norm *= -1
                            dy_norm *= -1
                        slope = (dy_norm, dx_norm)
                    
                    slopes[slope] += 1
                    curr_max = max(curr_max, slopes[slope])
            max_points = max(max_points, curr_max + same)
        return max_points