Geometry
Array
Hash Table
Math
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 <= 300
points[i].length == 2
-104 <= xi , yi <= 104
All the points
are unique .
Solutions
Solution 1
Python3 Java C++ Go C#
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
Python3 Java C++ Go
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 )
}
GitHub