> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/max-points-on-a-line.md).

# 149. Max Points on a Line

### Description

 Given *n* points on a 2D plane, find the maximum number of points that lie on the same straight line.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/max-points-on-a-line/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[\[1, 1], \[2, 2], \[3, 3]]

**Output:** 3

**Explanation:**

<div align="left"><img src="/files/-MHbNC4bGAio8D6Qw_1Q" alt=""></div>
{% endtab %}

{% tab title="Example 2" %}
**Input:** \[\[1, 1], \[3, 2], \[5, 3], \[4, 1], \[2, 3], \[1, 4]]

**Output:** 4

**Explanation:**

<div align="left"><img src="/files/-MHbNZaSNcWqpRTrYzPr" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n <= 1) return n;
        
        Map<String, Integer> slopeMap = new HashMap();
        int max = 0;
        
        for(int i = 0; i < n; i++) {
            int duplicate = 0;
            int tmpMax = 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) {
                    duplicate++;
                } else {
                    String slope = getSlopeKey(dx, dy);
                    slopeMap.put(slope, slopeMap.getOrDefault(slope, 0)+1);
                    tmpMax = Math.max(tmpMax, slopeMap.get(slope));
                }
            }
            max = Math.max(max, tmpMax+duplicate+1);
            slopeMap.clear();
        }
        
        return max;
    }
    
    private String getSlopeKey(int dx, int dy) {
        if(dx == 0) return "0-1";
        if(dy == 0) return "1-0";
        int d = gcd(dx, dy);
        return (dx/d) + "-" + (dy/d);
    }
    
    private int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a%b);
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*