# Max Points on a Line
**Difficulty:** HARD
[External](https://leetcode.com/problems/max-points-on-a-line)
Canonical: https://scaleengineer.com/dsa/problems/max-points-on-a-line
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array, Hash Table
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Citadel](https://scaleengineer.com/companies/citadel), [X](https://scaleengineer.com/companies/x), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Waymo](https://scaleengineer.com/companies/waymo)
---
## Problem
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 1:**

![](https://assets.glich.co/dsa/max-points-on-a-line/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/max-points-on-a-line/image1.jpg) 

**Input:** points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
**Output:** 4

**Constraints:**

* `1 <= points.length <= 300`
* `points[i].length == 2`
* `-104 <= xi, yi <= 104`
* All the `points` are **unique**.

# Approaches
## Brute Force Triplet Check
This approach uses a straightforward brute-force method. It considers every possible pair of points to define a line and then iterates through all other points to count how many are collinear with that line. This process is repeated for all pairs, and the maximum count is stored.
**Time:** O(N^3) · **Space:** O(1)
**Pros:** Simple to conceptualize and implement.; Avoids floating-point arithmetic, making it robust against precision issues.
**Cons:** High time complexity of O(N^3), which may be too slow for larger inputs (though it might pass for N=300).; Highly redundant, as it recomputes the count for the same line multiple times for different pairs of points on that line.
### Explanation
The fundamental idea is that three points `(x1, y1)`, `(x2, y2)`, and `(x3, y3)` are collinear if the slope between `(x1, y1)` and `(x2, y2)` is the same as the slope between `(x1, y1)` and `(x3, y3)`. To avoid division by zero for vertical lines and floating-point precision errors, we use the cross-multiplication form of the slope equality check: `(y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)`.

The algorithm iterates through every pair of points `(i, j)` to define a line. For each such line, it then performs a full scan of all points `k` in the dataset to count how many lie on this specific line. The maximum count found throughout this process is the result. Using `long` for the intermediate products in the cross-multiplication is a safeguard against potential integer overflow, although for the given constraints, `int` might suffice.

Here is the Java implementation:
```java
class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentCount = 0;
                // Define a line with points i and j, and count all points on it
                for (int k = 0; k < n; k++) {
                    long x1 = points[i][0], y1 = points[i][1];
                    long x2 = points[j][0], y2 = points[j][1];
                    long x3 = points[k][0], y3 = points[k][1];
                    // Check if point k is collinear with i and j
                    if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)) {
                        currentCount++;
                    }
                }
                maxCount = Math.max(maxCount, currentCount);
            }
        }
        return maxCount;
    }
}
```
### Algorithm
*   If the number of points `n` is less than or equal to 2, return `n`.
*   Initialize a variable `maxCount` to 0.
*   Iterate through all pairs of points `(i, j)` to define a line.
*   For each line defined by `points[i]` and `points[j]`, initialize a `currentCount` to 0.
*   Iterate through all points `k` from `0` to `n-1`.
*   Check if point `k` is collinear with points `i` and `j` using the cross-multiplication formula.
*   If point `k` lies on the line, increment `currentCount`.
*   After checking all points `k`, update `maxCount = max(maxCount, currentCount)`.
*   Return `maxCount` after all pairs `(i, j)` have been checked.

## Optimized Approach using Hash Map
This optimized approach iterates through each point, treating it as an anchor. For each anchor, it calculates the slopes of the lines formed with all other points. A hash map is used to count the number of points that share the same slope relative to the anchor. The maximum count for any anchor determines the overall maximum number of points on a line.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Much more efficient with a time complexity of O(N^2).; Robustly handles slope calculations using GCD, avoiding floating-point errors.
**Cons:** Requires extra O(N) space for the hash map.; Implementation is more complex due to handling slope representation (GCD, vertical lines).
### Explanation
This approach improves the time complexity to O(N^2) by avoiding the third nested loop. The core idea is that all points that are collinear with a given anchor point `p_i` will have the same slope with respect to `p_i`.

We iterate through each point `p_i` and fix it as an anchor. Then, for this `p_i`, we iterate through all subsequent points `p_j` (`j > i`). For each pair `(p_i, p_j)`, we calculate the slope. A crucial part of this approach is how we represent the slope to use it as a key in a hash map. Using floating-point numbers (`double`) for slopes is unreliable due to precision issues. A robust method is to represent the slope as a simplified fraction `dy/dx`. We compute `dy = y_j - y_i` and `dx = x_j - x_i`, find their Greatest Common Divisor (GCD), and use the string `"(dy/gcd)/(dx/gcd)"` as the map key. Vertical lines, where `dx = 0`, are a special case and can be represented by a constant string like `"infinity"`.

The hash map stores the number of points found for each unique slope relative to the anchor `p_i`. After checking all other points against `p_i`, the maximum value in the map gives the maximum number of other points on a single line through `p_i`. We add 1 to this count (for `p_i` itself) and update our global maximum. By repeating this for every possible anchor point, we guarantee finding the overall maximum.

Here is the Java implementation:
```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int maxPoints = 1;

        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeMap = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                int dy = points[j][1] - points[i][1];
                int dx = points[j][0] - points[i][0];
                
                String slope;
                if (dx == 0) {
                    // Vertical line
                    slope = "inf";
                } else {
                    int commonDivisor = gcd(dy, dx);
                    slope = (dy / commonDivisor) + "/" + (dx / commonDivisor);
                }
                
                slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
            }
            
            int currentMax = 0;
            for (int count : slopeMap.values()) {
                currentMax = Math.max(currentMax, count);
            }
            // Add the anchor point itself
            maxPoints = Math.max(maxPoints, currentMax + 1);
        }
        return maxPoints;
    }

    // Helper function to compute GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
*   Let `n` be the number of points. If `n <= 2`, return `n`.
*   Initialize `maxPoints = 1`.
*   Iterate through each point `p_i` from `i = 0` to `n-1`, using it as an anchor point.
*   For each anchor `p_i`, create a `HashMap<String, Integer>` to store counts of points per slope.
*   Iterate through every other point `p_j` from `j = i + 1` to `n-1`.
*   Calculate the slope between `p_i` and `p_j`. To handle slopes accurately:
    *   Represent vertical lines (where `dx = 0`) with a special string like `"inf"`.
    *   For other slopes, calculate `dy` and `dx`, find their Greatest Common Divisor (GCD), and use the reduced fraction `(dy/gcd) + "/" + (dx/gcd)` as the key.
*   Increment the count for the corresponding slope in the hash map.
*   After iterating through all `j` for a fixed `i`, find the maximum count (`localMax`) in the hash map.
*   The total points on the best line through `p_i` is `localMax + 1` (including `p_i`). Update the global `maxPoints` with this value if it's larger.
*   After iterating through all anchors `i`, return `maxPoints`.

# Solutions
### CSharp

```csharp
public class Solution { public int MaxPoints ( int [][] points ) { int n = points . Length ; int ans = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ]; for ( int j = i + 1 ; j < n ; ++ j ) { int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ]; int cnt = 2 ; for ( int k = j + 1 ; k < n ; ++ k ) { int x3 = points [ k ][ 0 ], y3 = points [ k ][ 1 ]; int a = ( y2 - y1 ) * ( x3 - x1 ); int b = ( y3 - y1 ) * ( x2 - x1 ); if ( a == b ) { ++ cnt ; } } if ( ans < cnt ) { ans = cnt ; } } } return ans ; } }
```

### Java

```java
class Solution { public int maxPoints ( int [][] points ) { int n = points . length ; int ans = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ]; Map < String , Integer > cnt = new HashMap <>(); for ( int j = i + 1 ; j < n ; ++ j ) { int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ]; int dx = x2 - x1 , dy = y2 - y1 ; int g = gcd ( dx , dy ); String k = ( dx / g ) + "." + ( dy / g ); cnt . put ( k , cnt . getOrDefault ( k , 0 ) + 1 ); ans = Math . max ( ans , cnt . get ( k ) + 1 ); } } return ans ; } private int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } }
```

### Python

```python
class Solution : def maxPoints ( self , points : List [ List [ int ]]) -> int : def gcd ( a , b ): return a if b == 0 else gcd ( b , a % b ) n = len ( points ) ans = 1 for i in range ( n ): x1 , y1 = points [ i ] cnt = Counter () for j in range ( i + 1 , n ): x2 , y2 = points [ j ] dx , dy = x2 - x1 , y2 - y1 g = gcd ( dx , dy ) k = ( dx // g , dy // g ) cnt [ k ] += 1 ans = max ( ans , cnt [ k ] + 1 ) return ans
```

### CPP

```cpp
class Solution { public: int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } int maxPoints ( vector < vector < int >>& points ) { int n = points . size (); int ans = 1 ; for ( int i = 0 ; i < n ; ++ i ) { int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ]; unordered_map < string , int > cnt ; for ( int j = i + 1 ; j < n ; ++ j ) { int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ]; int dx = x2 - x1 , dy = y2 - y1 ; int g = gcd ( dx , dy ); string k = to_string ( dx / g ) + "." + to_string ( dy / g ); cnt [ k ] ++ ; ans = max ( ans , cnt [ k ] + 1 ); } } return ans ; } };
```