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:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Constraints:
1 <= points.length <= 300points[i].length == 2-104 <= xi, yi <= 104- All the
points are unique.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
n = len(points)
ans = 1
for i in range(n):
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
cnt = 2
for k in range(j + 1, n):
x3, y3 = points[k]
a = (y2 - y1) * (x3 - x1)
b = (y3 - y1) * (x2 - x1)
cnt += a == b
ans = max(ans, cnt)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
}
ans = Math.max(ans, cnt);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
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];
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);
cnt += a == b;
}
ans = max(ans, cnt);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func maxPoints(points [][]int) int {
n := len(points)
ans := 1
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
cnt := 2
for k := j + 1; k < n; k++ {
x3, y3 := points[k][0], points[k][1]
a := (y2 - y1) * (x3 - x1)
b := (y3 - y1) * (x2 - x1)
if a == b {
cnt++
}
}
if ans < cnt {
ans = cnt
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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;
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func maxPoints(points [][]int) int {
n := len(points)
ans := 1
type pair struct{ x, y int }
for i := 0; i < n; i++ {
x1, y1 := points[i][0], points[i][1]
cnt := map[pair]int{}
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
dx, dy := x2-x1, y2-y1
g := gcd(dx, dy)
k := pair{dx / g, dy / g}
cnt[k]++
if ans < cnt[k]+1 {
ans = cnt[k] + 1
}
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
