We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Points on a Line

Difficulty: Hard

Problem Description

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.

Key Insights

  • To determine if points are collinear, we can use the slope between pairs of points.
  • The slope can be represented as a fraction to avoid floating-point inaccuracies.
  • Utilize a hash map to count the occurrences of slopes for each point as the base point.
  • Handle vertical lines (undefined slope) separately.
  • The maximum count of points for any slope gives the result for that point.

Space and Time Complexity

Time Complexity: O(n^2) - For each point, we calculate slopes with all other points. Space Complexity: O(n) - We use a hash map to store slopes.

Solution

To solve the problem, we will iterate through each point and calculate the slope between that point and every other point. We will use a hash map to count how many points share the same slope with respect to the base point. The maximum value in this hash map will give us the number of points on the same line passing through the base point. We need to account for vertical lines as well.

Code Solutions

from collections import defaultdict
from math import gcd

def maxPoints(points):
    if len(points) <= 2:
        return len(points)
    
    def slope(p1, p2):
        dx = p2[0] - p1[0]
        dy = p2[1] - p1[1]
        if dx == 0:  # vertical line
            return ('inf', 0)
        g = gcd(dx, dy)
        return (dy // g, dx // g)  # return reduced slope

    max_points = 0

    for i in range(len(points)):
        slopes = defaultdict(int)
        for j in range(len(points)):
            if i != j:
                s = slope(points[i], points[j])
                slopes[s] += 1
        max_points = max(max_points, max(slopes.values(), default=0) + 1)

    return max_points
← Back to All Questions