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]], returntrue.

Example 2:

Givenpoints=[[1,1],[-1,-1]], returnfalse.

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

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

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.

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);
    }
};