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.length1 <= n <= 104-108 <= points[i][j] <= 108
Follow up: Could you do better than O(n2)?
Solutions
Solution 1
PythonJavaC++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)(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
