> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0149-max-points-on-a-line.md).

# 0149. Max Points on a Line

<https://leetcode.com/problems/max-points-on-a-line>

## 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*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/02/25/plane2.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**.

## ac

GCD calculation

```java
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        // edge case
        if (points == null || points.length == 0) return 0;
        if (points.length <= 2) return points.length;


        int res = 0;
        for (int i = 0; i < points.length; i++) {
            HashMap<String, Integer> map = new HashMap<>();
            int samePoint = 0;
            int sameXAxis = 1;
            // 3 scenarios: 1) samepoint; 2) in the same x axis; 3) has same slope
            for (int j = 0; j < points.length; j++) {
                // if (i == j) continue;
                if (i != j) {
                    // same point
                if (points[i].x == points[j].x && points[i].y == points[j].y) samePoint++;
                // same x axis
                if (points[i].x == points[j].x) {
                    sameXAxis++;
                    continue; // cannot calculate slope, continue
                }
                // slope
                int numerator = points[i].y - points[j].y;
                int denominator = points[i].x - points[j].x;
                int gcd = gcd(numerator, denominator);
                String hashStr = (numerator / gcd) + "/" + (denominator / gcd);
                map.put(hashStr, map.getOrDefault(hashStr, 1) + 1); // 2 points in same slope
                res = Math.max(res, map.get(hashStr) + samePoint);
                }

            }
            res = Math.max(res, sameXAxis);
        }

        return res;
    }

    private int gcd(int a, int b) {
        if(a == 0) return b;
        return gcd(b % a, a);
    }
}
```