# Leetcode: Max Points on a Line

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

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/max-points-on-a-line
// Basic Ideas: hashmap
// For each point check with others:
//   - Same point
//   - Vertical line
//   - Normal line: y=ax+b. We use (a, b) as key for the set
//
// Corner cases:
//  - Empty points
//  - One point
//  - All same points
//  - k is float:
//    [[0,0],[94911151,94911150],[94911152,94911151]]
//
// Complexity: Time O(n*n), Space O(1)
/**
* Definition for a point.
* type Point struct {
*     X int
*     Y int
* }
*/
func gcd(x int, y int) int {
if x == 0 { return y }
for y!=0 {
x, y = y, x%y
}
return x
}

func maxPoints(points []Point) int {
if len(points) <= 1 { return len(points) }
res := 0
for i, point1 := range points {
count := 1
k_map := map[string]int{}
// no need to loop all nodes
for j:=i+1; j<len(points); j++{
point2 := points[j]
if point1.X == point2.X && point1.Y == point2.Y {
// same point
count++
continue
}
if point1.X == point2.X {
// vertical line
k_map["INF"] += 1
} else {
// a x1+b = y1
// a x2+b = y2
// How to get a. a=(y2-y1)/(x2-x1)
diffY, diffX := point2.Y-point1.Y, point2.X-point1.X
g := gcd(diffX, diffY)
a, b := diffX/g, diffY/g
// fmt.Println("diffX", diffX, "a", a, "diffY", diffY, b, "g", g)
k_index := fmt.Sprintf("%d-%d", a, b)
k_map[k_index] += 1
}
}
// fmt.Println(i, k_map)
if len(k_map) == 0 {
if count>res { res = count }
} else {
for key := range k_map {
if k_map[key]+count>res { res = k_map[key]+count }
}
}
}
return res
}
```

Share It, If You Like It.