Max Points on a Line

149.Max Points on a Line

Math

Hash Table

Geometry

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:

Input:

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

→

Output:

3

Algorithm:

1. For each point, calculate slopes with others
2. Use HashMap to track points with same slope
3. Handle vertical and horizontal lines
4. Return maximum count plus one (current point)

Complexity:

Time: O(n²) | Space: O(n)

Java Solution:

public int maxPoints(int[][] points) {
    int n = points.length;
    
    if (n == 1) return 1;
    
    int max = 0;    
    
    for (int i = 0; i < n; i++) {
        Map<Double, Integer> map = new HashMap<>();  // Track slopes
        for (int j = i + 1; j < n; j++) {
            double slope = calculateSlope(points[i], points[j]);
            
            map.put(slope, map.getOrDefault(slope, 0) + 1);
        
            max = Math.max(max, map.get(slope));
        }    
    }

    return max + 1;  // Add 1 for current point
}

private double calculateSlope(int[] p1, int[] p2) {
    int x1 = p1[0], x2 = p2[0];
    int y1 = p1[1], y2 = p2[1];
    
    if (x1 == x2) return Double.MAX_VALUE;  // Vertical line
    if (y1 == y2) return 0;  // Horizontal line
    return (double) (y2 - y1) / (double) (x2 - x1);
}

Python Solution:

def maxPoints(self, points: List[List[int]]) -> int:
    n = len(points)
    if n <= 2: return n
    
    def slope(p1: List[int], p2: List[int]) -> float:
        x1, y1 = p1
        x2, y2 = p2
        if x1 == x2: return float('inf')
        if y1 == y2: return 0
        return (y2 - y1) / (x2 - x1)
    
    max_points = 1
    for i in range(n):
        slopes = collections.defaultdict(int)
        for j in range(i + 1, n):
            s = slope(points[i], points[j])
            slopes[s] += 1
            max_points = max(max_points, slopes[s] + 1)
            
    return max_points

C++ Solution:

class Solution {
public:
    double calculateSlope(int* p1, int* p2) {
        if (p1[0] == p2[0]) return DBL_MAX;
        if (p1[1] == p2[1]) return 0;
        return (double)(p2[1] - p1[1]) / (p2[0] - p1[0]);
    }
    
    int maxPoints(vectorint>>& points) {
        int n = points.size();
        if (n <= 2) return n;
        
        int maxPoints = 1;
        for(int i = 0; i < n; i++) {
            unordered_map<double, int> slopes;
            for(int j = i + 1; j < n; j++) {
                double slope = calculateSlope(&points[i][0], &points[j][0]);
                slopes[slope]++;
                maxPoints = max(maxPoints, slopes[slope] + 1);
            }
        }
        
        return maxPoints;
    }
};