# 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:**

Givenpoints=`[[1,1],[-1,1]]`, return`true`.

**Example 2:**

Givenpoints=`[[1,1],[-1,-1]]`, return`false`.

**Follow up:**\
Could you do better than O(n^2)?

**The Idea:** First iterate through the list of points to find the most left and the most right x coordinates. The respected axis for between these two points must be 1/2 the distance between these points from left coordinate. It also must follow that the remaining points are a reflection of this axis. In order compare against this axis, I allocated an `unordered_set` of points, so that I can quickly lookup any point by its unique string permutation (x,y). So then, in order to verify the reflection, I iterate through each point and check to see whether its reflected analog exists through in the `unordered_set` through a simple lookup. If all the reflected analogs exists, return true.

There are a few edge cases:\
1\. Empty set is a valid reflection.\
2\. Checking for points that exist along the axis of reflection.

**Time Complexity:** O(n) time and space

```cpp
struct pair_hash {
    inline std::size_t operator()(const std::pair<int, int> & v) const {
        return hash<string>{}(to_string(v.first) + to_string(v.second));
    }
};

unordered_set<pair<int, int>, pair_hash> add_to_set(const vector<pair<int, int>> &points) {
    unordered_set<pair<int, int>, pair_hash> unique_points;
    unique_points.reserve(points.size());

    for (auto p : points)
        unique_points.insert(p);

    return unique_points;
}

pair<int, int> min_and_max_x_val(const vector<pair<int, int>>& points) {
    int my_min = INT_MAX, my_max = INT_MIN;
    for (auto &p : points) {
        my_min = min(my_min, p.first);
        my_max = max(my_max, p.first);
    }
    return {my_min, my_max};
}

bool isReflected(vector<pair<int, int>>& points) {
    if (points.empty()) return true;

    pair<int, int> min_max_x = min_and_max_x_val(points);
    if (min_max_x.first == min_max_x.second) return true; // TODO: try without this later as well

    double verify_this_y_axis = (abs(min_max_x.second - min_max_x.first) / 2.0) + min_max_x.first;
    unordered_set<pair<int, int>, pair_hash> unique_points = add_to_set(points);

    for (auto p : unique_points) {
        double dist_to_axis = abs(verify_this_y_axis - p.first);
        pair<int, int> reflected_analog;
        if (p.first <= verify_this_y_axis) 
            reflected_analog = {p.first + (dist_to_axis) * 2, p.second};
        else reflected_analog = { p.first - (dist_to_axis) * 2, p.second };

        if (unique_points.find(reflected_analog) == unique_points.end())
            return false;
    }

    return true;
}
```

**Testing**

```cpp
int main()
{
    vector<pair<int, int>> points1 = { { 1,1 },{ -1,1 } };
    cout << boolalpha << isReflected(points1) << endl; // T

    vector<pair<int, int>> points2 = { { 1,1 },{ -1,-1 } };
    cout << boolalpha << isReflected(points2) << endl; // F

    vector<pair<int, int>> points3 = { { 0,0 },{ 1,0 } }; 
    cout << boolalpha << isReflected(points3) << endl; // T

    vector<pair<int, int>> points4 = { { -2,0 },{ -1,1 },{ 1,1 },{ 2,0 }, { 1,-1 },{ -1,-1 } };
    cout << boolalpha << isReflected(points4) << endl; // T

    vector<pair<int, int>> points5 = { { -2,0 }, {1,2}, { -1,1 },{ 1,1 },{ 2,0 },{ 1,-1 },{ -1,-1 } };
    cout << boolalpha << isReflected(points5) << endl; // F

    vector<pair<int, int>> points6 = { { 1, 1 }, {-4, 1} };
    cout << boolalpha << isReflected(points6) << endl; // T

    vector<pair<int, int>> points7 = { {10, 10},{11, 11},{9, 11} };
    cout << boolalpha << isReflected(points7) << endl; // T

}
```

**Update:**

The previous submission performed in 21 percentile range. Updating the hash function to the follow improved performance to 75 percentile.

```cpp
struct pair_hash {
    inline std::size_t operator()(const std::pair<int, int> & v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/356-line-reflection.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.