## Monday, June 13, 2016

### LeetCode 356 - Line Reflection

[LeetCode] Line Reflection 直线对称 - Grandyang - 博客园
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given set of points.
Example 1:

Given points = `[[1,1],[-1,1]]`, return `true`.
Example 2:

Given points = `[[1,1],[-1,-1]]`, return `false`.
Could you do better than O(n2)?
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.
Cases:  duplicate points
http://blog.csdn.net/jmspan/article/details/51688862

http://dartmooryao.blogspot.com/2016/06/leetcode-356-line-reflection.html
https://leetcode.com/discuss/108319/simple-java-hashset-solution
The idea is that all symmetry pair of number's x value will add to the same number.
So we want to find out this number by finding the min and max, then add them

In addition, we use a string to represent the points.
For each point, we calculate the counter part of this point, and check whether this string exists in the set. If not, return false. If all points pass the check, return true.

My idea is similar to it. However, in my solution, I have to either add or subtract the number. Also, I have to deal with double value because I use average of the two value. Which is more difficult to handle.

Very important:
(1) Use sum over average!
(2) Consider using min/max value when I need to find a particular value from a group of numbers.
(3) String matching is magic!
public boolean isReflected(int[][] points) { int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; HashSet<String> set = new HashSet<>(); for(int[] p:points){ max = Math.max(max,p[0]); min = Math.min(min,p[0]); String str = p[0] + "a" + p[1]; set.add(str); } int sum = max+min; for(int[] p:points){ //int[] arr = {sum-p[0],p[1]}; String str = (sum-p[0]) + "a" + p[1]; if( !set.contains(str)) return false; } return true; }

https://discuss.leetcode.com/topic/48172/simple-java-hashset-solution/5
``````    public boolean isReflected(int[][] points) {
int max, min, sum;
HashSet<Point> set = new HashSet<>();
if(points.length == 0) return true;
max = points[0][0]; min = max;
for(int[] point: points) {
int x = point[0];
if(x > max) max = x;
if(x < min) min = x;
}
sum = (max + min);
for(int[] point: points) {
Point ref = new Point(sum - point[0], point[1]);
if(set.contains(ref)) set.remove(ref);
}
return set.isEmpty();

}
private class Point {
int x;
int y;
Point(int xx, int yy) {x = xx; y = yy;}
@Override
public boolean equals(Object obj){
Point p = (Point) obj;
return (this.x == p.x && this.y == p.y);
}
@Override
public int hashCode(){
return x * 31 + y * 17;
}
}``````

https://leetcode.com/discuss/107725/8ms-java-no-hash-just-sort-o-1-space
Thanks for StefanPochmann's test case. I found that average solution does not work for odd points. As the example StefanPochmann provided [[0,0],[1,0],[3,0]]. There is no reflection line. With average code, it returns true.
So after read the hint and StefanPochmann's solution, I made it with Java.
Just sort the points with x. Then "reflect" it by assume there is a x-axis formed by minx and maxx. Then resorted the array. All the points should be same as the first sort.
public boolean isReflected(int[][] points) { if (points == null) { return false; } Arrays.sort(points, new ArrComparator()); int[][] reflectedPoints = new int[points.length][2]; for (int i = 0; i < reflectedPoints.length; i++) { reflectedPoints[i][0] = points[0][0] + points[reflectedPoints.length-1][0] - points[i][0]; reflectedPoints[i][1] = points[i][1]; } Arrays.sort(reflectedPoints, new ArrComparator()); for (int i = 0; i < reflectedPoints.length; i++) { if (reflectedPoints[i][0] != points[i][0] || reflectedPoints[i][1] != points[i][1]) { return false; } } return true; } public class ArrComparator implements Comparator<int[]>{ @Override public int compare(int[] a, int b[]) { if (a[0] == b[0]) { return Integer.compare(a[1], b[1]); } return Integer.compare(a[0], b[0]); } }
My first approach to solve this problem was to sort all points by its x-coordinates, find the mid point of all points and then use 2-pointer to iterate through the sorted points from both side, and check if they are symmetric.
It turn out this approach is a pain in the neck. Because sorting all points is not easy. The compare function used in sorting depends on where the middle line is. If you are not convinced, please think about how to compare 2 points that have the same x-coordinate.

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

```    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;
}
```
http://blog.csdn.net/github_34333284/article/details/51697208
Think that, if all points are reflect each other. We need to first find the line. The line should be in the middle of (min, max). For other points, if two point reflect, the y-ith should be same, (min, max) / 2 - x1 = (min, max) / 2 - x2. */ bool isReflected(vector< pair<int, int> >& points) { unordered_map< int, set<int> > m; int minX = INT_MAX, maxX = INT_MIN; for(int i = 0; i < points.size(); ++i) { minX = min(points[i].first, minX); maxX = max(points[i].first, maxX); m[points[i].first].insert(points[i].second); } double y = double(maxX + minX) / 2; for(int i = 0; i < points.size(); ++i) { int t = 2*y - points[i].first; if(!m.count(t) || !m[t].count(points[i].second)) return false; } return true; } // second method bool isReflectedII(vector<pair<int, int> >& points) { if(point.size() == 0) return true; set< pair<int, int> > res; double y = 0; for(auto a : points) { res.insert(a); y += a.first; } y = y / points.size(); for(auto a : res) { if(!res.count((2 * y - a.first), a.second)) return false; } return true; }

[Solution]

[Mistake]

[Solution]

[Solution #1]

Cons: 由于ConcurrentModificationException, 使得实现起来稍微麻烦一点。
[Solution #2]

A.x + B.x === xMin + xMax, if A and B are symmetrical to each other.

[Solution #3]

idea就是把所有点表示成一个string, 比如x#y，然后把所有点的string加入到HashSet里，在找对称点的时候只要找set里是否存在(sum – x)#y这样的string就可以了。
[Time & Space]
O(n) time, O(n) space
Code is for Solution #2
`  ``public` `boolean` `isReflected(``int``[][] points) {`
`    ``if` `(points.length == ``0``) {`
`      ``return` `true``;`
`    ``}`
`    ``int` `xMin = Integer.MAX_VALUE;`
`    ``int` `xMax = Integer.MIN_VALUE;`
`    ``Map<Integer, Set<Integer>> yGroup = ``new` `HashMap<>();`
`    ``for` `(``int` `i = ``0``; i < points.length; i++) {`
`      ``xMin = Math.min(xMin, points[i][``0``]);`
`      ``xMax = Math.max(xMax, points[i][``0``]);`
`      ``yGroup.putIfAbsent(points[i][``1``], ``new` `HashSet<>());`
`      ``yGroup.get(points[i][``1``]).add(points[i][``0``]);`
`    ``}`
`    ``int` `sum = xMax + xMin;`
`    ``for` `(``int` `y : yGroup.keySet()) {`
`      ``Set<Integer> set = yGroup.get(y);`
`      ``for` `(``int` `x : set) {`
`        ``if` `(!set.contains(sum - x)) {`
`          ``return` `false``;`
`        ``}`
`      ``}`
`    ``}`
`    ``return` `true``;`
`  ``}`

2. LC 356, 但是直线可以是任意直线