[LeetCode] Line Reflection

356. Line Reflection

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect 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 set of the original points is the same that the reflected ones.

Note that there can be repeated points.

Follow up:
Could you do better than O(n2) ?

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
28
29
class Solution {
struct myHash {
template <class T1, class T2>
size_t operator() (std::pair<T1, T2> const& pair) const {
size_t h1 = hash<T1>()(pair.first);
size_t h2 = hash<T2>()(pair.second);

return h1 ^ h2;
}
};
public:
bool isReflected(vector<vector<int>>& points) {
unordered_set<pair<int, int>, myHash> hashSet;
int maxVal{points[0][0]}, minVal{points[0][0]};
for(auto& point : points) {
hashSet.insert({point[0], point[1]});
maxVal = max(maxVal, point[0]);
minVal = min(minVal, point[0]);
}

int y = maxVal + minVal;

for(auto& point : hashSet) {
if(!hashSet.count({y - point.first, point.second}))
return false;
}
return true;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/02/20/PS/LeetCode/line-reflection/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.