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);
}
};
Last modified 3yr ago