Max points on a line

149.Max Points on a Line

Math

Hash Table

Geometry

Problem Statement:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Points can be duplicates, and need to handle vertical lines and identical points.

Example:

Input:

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

→

Output:

3

All points lie on the same line y = x

Algorithm:

1. For each point, calculate slopes to all other points
2. Use HashMap to count points with same slope
3. Handle special cases: duplicates and vertical lines
4. Track maximum count including duplicates

Complexity:

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

Java Solution:

public int maxPoints(Point[] points) {
    if (points == null || points.length == 0) return 0;
    
    HashMap<Double, Integer> result = new HashMap<>();
    int max = 0;
    
    // For each point, calculate slopes with all other points
    for (int i = 0; i < points.length; i++) {
        int duplicate = 1;  // Count of identical points
        int vertical = 0;   // Count of points in vertical line
        
        for (int j = i + 1; j < points.length; j++) {
            // Handle vertical lines and duplicates
            if (points[i].x == points[j].x) {
                if (points[i].y == points[j].y) {
                    duplicate++;
                } else {
                    vertical++;
                }
            } else {
                // Calculate and store slope
                double slope = points[j].y == points[i].y ? 0.0
                    : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x);
                
                result.put(slope, result.getOrDefault(slope, 1) + 1);
            }
        }
        
        // Find max count including duplicates
        for (Integer count : result.values()) {
            max = Math.max(count + duplicate, max);
        }
        
        // Check vertical line count
        max = Math.max(vertical + duplicate, max);
        result.clear();
    }
    
    return max;
}

Python Solution:

def maxPoints(self, points: List[List[int]]) -> int:
    n = len(points)
    if n <= 2:
        return n
        
    max_points = 0
    
    # For each point, calculate slopes with all other points
    for i in range(n):
        slopes = defaultdict(int)
        duplicate = 1
        vertical = 0
        
        for j in range(i + 1, n):
            # Handle vertical lines and duplicates
            if points[i][0] == points[j][0]:
                if points[i][1] == points[j][1]:
                    duplicate += 1
                else:
                    vertical += 1
            else:
                # Calculate slope
                dy = points[j][1] - points[i][1]
                dx = points[j][0] - points[i][0]
                slope = dy/dx if dx != 0 else float('inf')
                slopes[slope] += 1
        
        # Find max count including duplicates
        curr_max = max(slopes.values(), default=0) + duplicate
        max_points = max(max_points, curr_max, vertical + duplicate)
        
    return max_points

C++ Solution:

int maxPoints(vector& points) {
    if (points.empty()) return 0;
    
    unordered_map<double, int> result;
    int max_points = 0;
    
    // For each point, calculate slopes with all other points
    for (int i = 0; i < points.size(); i++) {
        int duplicate = 1;
        int vertical = 0;
        result.clear();
        
        for (int j = i + 1; j < points.size(); j++) {
            // Handle vertical lines and duplicates
            if (points[i].x == points[j].x) {
                if (points[i].y == points[j].y) {
                    duplicate++;
                } else {
                    vertical++;
                }
            } else {
                // Calculate slope
                double slope = points[j].y == points[i].y ? 0.0
                    : 1.0 * (points[j].y - points[i].y) / (points[j].x - points[i].x);
                result[slope]++;
            }
        }
        
        // Find max count including duplicates
        for (auto& p : result) {
            max_points = max(max_points, p.second + duplicate);
        }
        max_points = max(max_points, vertical + duplicate);
    }
    
    return max_points;
}