Max Points on a Line

MathHash Table

30 min

Problem Statement

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example

Example 1:

Input: points = [[1,1],[2,2],[3,3]]

Given points: [[1,1],[2,2],[3,3]]

Max points on a line: 3

Output: 3

Solution (Using Slopes)

A common approach to this problem is to iterate through each point and, for each point, calculate the slopes with all other points. We can use a hash map to store the counts of each slope. The maximum number of points on a line for a given starting point will be the maximum count in the hash map plus any duplicate points.

Algorithm Steps

Iterate through each point i as a potential starting point of a line.
For each starting point i, create a hash map to store slopes with other points.
Iterate through the rest of the points j.
Calculate the slope between point i and point j. Handle vertical lines and duplicate points.
Store the slope and its count in the hash map.
The maximum number of points for the line starting at i is the max count in the map plus any duplicates.
Keep track of the global maximum as you iterate through all starting points.

Points:

Slopes from point -1: {}

Max Points: 0

Start.

Max Points on a Line Solution


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 2:
            return n
        
        max_points = 0
        for i in range(n):
            slopes = {}
            duplicates = 1
            for j in range(i + 1, n):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                
                if dx == 0 and dy == 0:
                    duplicates += 1
                    continue
                
                slope = dy / dx if dx != 0 else float('inf')
                slopes[slope] = slopes.get(slope, 0) + 1
            
            max_points = max(max_points, duplicates)
            for slope in slopes:
                max_points = max(max_points, slopes[slope] + duplicates)
                
        return max_points