356

356. Line Reflection (Medium)

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)?

Companies: Yandex, Google

Related Topics:
Array, Hash Table, Math

Similar Questions:

• Max Points on a Line (Hard)
• Number of Boomerangs (Medium)

Hints:

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

Solution 1.

// OJ: https://leetcode.com/problems/line-reflection
// Author: github.com/lzl124631x
// Time: O((logN)^2 + N)
// Space: O(N)
class Solution {
public:
    bool isReflected(vector<vector<int>>& A) {
        map<int, set<int>> m;
        for (auto &p : A) m[p[0]].insert(p[1]);
        long long minX = m.begin()->first, maxX = m.rbegin()->first, sumX = minX + maxX;
        auto L = m.begin();
        auto R = m.rbegin();
        for (; L != m.end() && L->first <= R->first; ++L, ++R) {
            long long lx = L->first, rx = R->first;
            if (lx + rx != sumX) return false;
            auto &lys = L->second, &rys = R->second;
            if (lys != rys) return false;
        }
        return true;
    }
};