Array
Hash Table
Math
Description
Given n
points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically.
In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.
Note that there can be repeated points.
Example 1:
Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.
Example 2:
Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.
Constraints:
n == points.length
1 <= n <= 104
-108 <= points[i][j] <= 108
Follow up: Could you do better than O(n2 )
?
Solutions
Solution 1
Python3 Java C++ Go
class Solution :
def isReflected ( self , points : List [ List [ int ]]) -> bool :
min_x , max_x = inf , - inf
point_set = set ()
for x , y in points :
min_x = min ( min_x , x )
max_x = max ( max_x , x )
point_set . add (( x , y ))
s = min_x + max_x
return all (( s - x , y ) in point_set for x , y in points )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public boolean isReflected ( int [][] points ) {
final int inf = 1 << 30 ;
int minX = inf , maxX = - inf ;
Set < List < Integer >> pointSet = new HashSet <> ();
for ( int [] p : points ) {
minX = Math . min ( minX , p [ 0 ] );
maxX = Math . max ( maxX , p [ 0 ] );
pointSet . add ( List . of ( p [ 0 ] , p [ 1 ] ));
}
int s = minX + maxX ;
for ( int [] p : points ) {
if ( ! pointSet . contains ( List . of ( s - p [ 0 ] , p [ 1 ] ))) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
bool isReflected ( vector < vector < int >>& points ) {
const int inf = 1 << 30 ;
int minX = inf , maxX = - inf ;
set < pair < int , int >> pointSet ;
for ( auto & p : points ) {
minX = min ( minX , p [ 0 ]);
maxX = max ( maxX , p [ 0 ]);
pointSet . insert ({ p [ 0 ], p [ 1 ]});
}
int s = minX + maxX ;
for ( auto & p : points ) {
if ( ! pointSet . count ({ s - p [ 0 ], p [ 1 ]})) {
return false ;
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 func isReflected ( points [][] int ) bool {
const inf = 1 << 30
minX , maxX := inf , - inf
pointSet := map [[ 2 ] int ] bool {}
for _ , p := range points {
minX = min ( minX , p [ 0 ])
maxX = max ( maxX , p [ 0 ])
pointSet [[ 2 ] int { p [ 0 ], p [ 1 ]}] = true
}
s := minX + maxX
for _ , p := range points {
if ! pointSet [[ 2 ] int { s - p [ 0 ], p [ 1 ]}] {
return false
}
}
return true
}
GitHub