Problem Description

The "Max Points on a Line" problem asks you to determine the maximum number of points that lie on the same straight line, given a set of points in a 2D plane. Each point is represented as an integer pair [x, y]. The input is an array points where points[i] = [x_i, y_i].

• All points are distinct.
• You must find the largest number of points that are collinear (i.e., lie on the same straight line).
• There is no explicit restriction on reusing points, but each point is only counted once.

Your task is to return an integer representing the maximum number of points that can be found on a single straight line.

Thought Process

At first glance, the brute-force approach comes to mind: for every pair of points, check how many other points are collinear with them. However, this would involve checking all possible lines defined by every pair of points and counting, which is computationally expensive.

To optimize, we can observe that:

• Every line can be uniquely identified by its slope (and intercept), but for our purposes, using slope is sufficient.
• If we fix one point and compute the slopes it forms with every other point, then points with the same slope (relative to the fixed point) are collinear with it.
• Thus, for each point, we can count the maximum number of points sharing the same slope with it.

Solution Approach

We solve the problem by iterating through each point and, for each, computing the slope it forms with every other point. We use a hash map (dictionary) to count how many times each slope occurs. The steps are:

1. Iterate through each point i:
   • Initialize a hash map to count slopes.
   • Track duplicates (points with the same coordinates as i).
2. For every other point j:
   • If j is the same as i, increment duplicates.
   • Otherwise, compute the slope between i and j:
     • Handle vertical lines (infinite slope) and horizontal lines (zero slope) as special cases.
     • To avoid floating point precision errors, represent slopes as reduced fractions using the greatest common divisor (GCD).
   • Increment the count for this slope in the hash map.
3. Compute the maximum:
   • The maximum number of points on a line through i is the highest slope count plus duplicates (including i itself).
   • Update the global maximum accordingly.

We repeat this process for every point and return the global maximum.

Example Walkthrough

Let's use the input points = [[1,1],[2,2],[3,3],[4,2],[5,1]].

1. Start with point [1,1]:
   • Compute slopes to all other points:
   • • To [2,2]: slope = (2-1)/(2-1) = 1
     • To [3,3]: slope = (3-1)/(3-1) = 1
     • To [4,2]: slope = (2-1)/(4-1) = 1/3
     • To [5,1]: slope = (1-1)/(5-1) = 0
   • Slopes: {1: 2, 1/3: 1, 0: 1}
   • Max with [1,1]: 2 (for slope 1) + 1 (itself) = 3
2. Repeat for [2,2]:
   • Slopes: {1: 1, 0: 1, -1: 1}
   • Max with [2,2]: 1 + 1 = 2
3. Repeat for [3,3]:
   • Slopes: {-1/2: 1, -1: 1, -2/3: 1}
   • Max with [3,3]: 1 + 1 = 2
4. Repeat for [4,2] and [5,1]:
   • Each will have a max of 2 points on a line with them.
5. Result:
   • The maximum is 3 (points [1,1], [2,2], [3,3] are collinear).

Time and Space Complexity

Brute-force approach:

• For every pair of points, check all other points for collinearity. This is O(n^3).

• For each point, compute slopes to every other point: O(n^2).
• Each slope calculation and hash map operation is O(1) on average.
• Total time complexity: O(n^2).
• Space complexity: O(n) for the hash map of slopes for each anchor point.

Summary

The key insight is that collinear points share the same slope with respect to a fixed anchor. By iterating through each point and counting the number of points with the same slope, we efficiently find the largest set of collinear points. Using hash maps for slope counting, and representing slopes as reduced fractions, ensures accuracy and speed. This approach is both elegant and efficient, reducing the naive cubic complexity to quadratic.

Code Implementation

from collections import defaultdict
from math import gcd

class Solution:
    def maxPoints(self, points):
        if not points:
            return 0
        n = len(points)
        result = 1
        for i in range(n):
            slopes = defaultdict(int)
            duplicates = 0
            max_points = 0
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                dx = x2 - x1
                dy = y2 - y1
                if dx == 0 and dy == 0:
                    duplicates += 1
                    continue
                g = gcd(dx, dy)
                # Reduce the slope to its simplest form
                slope = (dy // g, dx // g)
                slopes[slope] += 1
                max_points = max(max_points, slopes[slope])
            result = max(result, max_points + duplicates + 1)
        return result
      

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <utility>
using namespace std;

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        int n = points.size(), result = 1;
        for (int i = 0; i < n; ++i) {
            unordered_map<long long, int> slope_count;
            int duplicates = 0, max_points = 0;
            for (int j = i + 1; j < n; ++j) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) {
                    ++duplicates;
                    continue;
                }
                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                // To avoid hash collision, combine dx and dy into one key
                long long key = ((long long)dx) * 1000000007 + dy;
                slope_count[key]++;
                max_points = max(max_points, slope_count[key]);
            }
            result = max(result, max_points + duplicates + 1);
        }
        return result;
    }
private:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};
      

import java.util.*;

class Solution {
    public int maxPoints(int[][] points) {
        if (points.length == 0) return 0;
        int n = points.length, result = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            int duplicates = 0, maxPoints = 0;
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                int g = gcd(dx, dy);
                dx /= g;
                dy /= g;
                String slope = dx + "/" + dy;
                slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
                maxPoints = Math.max(maxPoints, slopeMap.get(slope));
            }
            result = Math.max(result, maxPoints + duplicates + 1);
        }
        return result;
    }
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
      

function maxPoints(points) {
    if (points.length === 0) return 0;
    let n = points.length, result = 1;
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    for (let i = 0; i < n; i++) {
        let slopes = {};
        let duplicates = 0, maxPoints = 0;
        let [x1, y1] = points[i];
        for (let j = i + 1; j < n; j++) {
            let [x2, y2] = points[j];
            let dx = x2 - x1, dy = y2 - y1;
            if (dx === 0 && dy === 0) {
                duplicates++;
                continue;
            }
            let g = gcd(dx, dy);
            let slope = (dy / g) + '/' + (dx / g);
            slopes[slope] = (slopes[slope] || 0) + 1;
            maxPoints = Math.max(maxPoints, slopes[slope]);
        }
        result = Math.max(result, maxPoints + duplicates + 1);
    }
    return result;
}