# 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.

Example 1:

``````Input: [[1,1],[-1,1]]
Output: true
``````

Example 2:

``````Input: [[1,1],[-1,-1]]
Output: false
``````

Could you do better than O( n 2) ?

Hint:

1. Find the smallest and largest x-value for all points.
2. If there is a line then it should be at y = (minX + maxX) / 2.
3. For each point, make sure that it has a reflected point in the opposite side.

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

``````class Solution {
public:
bool isReflected(vector<pair<int, int>>& points) {
unordered_map<int, set<int>> m;
int mx = INT_MIN, mn = INT_MAX;
for (auto a : points) {
mx = max(mx, a.first);
mn = min(mn, a.first);
m[a.first].insert(a.second);
}
double y = (double)(mx + mn) / 2;
for (auto a : points) {
int t = 2 * y - a.first;
if (!m.count(t) || !m[t].count(a.second)) {
return false;
}
}
return true;
}
};
``````

``````class Solution {
public:
bool isReflected(vector<pair<int, int>>& points) {
if (points.empty()) return true;
set<pair<int, int>> pts;
double y = 0;
for (auto a : points) {
pts.insert(a);
y += a.first;
}
y /= points.size();
for (auto a : pts) {
if (!pts.count({y * 2 - a.first, a.second})) {
return false;
}
}
return true;
}
};
``````

Max Points on a Line

https://leetcode.com/problems/line-reflection/description/

https://leetcode.com/discuss/107661/48-ms-short-c-solution

https://leetcode.com/discuss/107761/group-by-y-then-sort-by-x-17ms

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation