LeetCode: Line Reflection

/**
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflects the given points.

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

Follow up:
Could you do better than O(n2)?
*/
import java.util.*;

class Point{
double x, y;
Point(double x1, double y1){
x = x1;
y = y1;
}
public String toString(){
return "("+x+","+y+")";
}
}
public class LineReflection{
/**
-use two loops
-for the first point, find the widest possible x value, use this point to define the mid-value
-for each point, find a point to form a pair that satisfies the earlier found mid-value
-if no pair found or if this pair has different mid-value than the earlier found ones, return false
O(n^2), O(1)
*/
public static boolean checkReflection1(Point[] points){
if(points==null || points.length<1){
return true;
}
Point mid = null;
for(int i=0;i<points.length; i++){
Point p1 = points[i];
double maxdist = Double.MIN_VALUE; Point ref = null;
for(int j=0;j<points.length; j++){
Point p2 = points[j];
if(p1.y==p2.y && p1.x!=p2.x){//same y value but not same point
if(mid==null){//first pairs define the mid value
double newdist = Math.abs(p1.x - p2.x);
if(newdist>maxdist){
maxdist = newdist;
//we found a best reflection point for p1
ref = p2;
}
}else{
//if mid was already found, check if the new pair satisfies the already found mid-value
if(Math.abs(p1.x - mid.x) == Math.abs(p2.x - mid.x)){
ref = p2;
}
}
}
}
//now lets define the mid with the best ref point
if(mid==null){
mid = new Point((p1.x+ref.x)/2.0, p1.y);
}else{
//check if the mid we found earlier matches with the one found just now
//no pair was found or the best pair found has different mid point
System.out.println("mid was:"+mid+" p1 is:"+p1+" ref is:"+ref);
if(ref==null || (ref.x+p1.x)/2.0!=mid.x){
return false;
}
}
}
return true;
}

/**
-use hashmap to put x as key and the set of y-values as value
-in pass1, find the leftmost x value and rightmost x value
-define the mid value using the leftmost x and rightmost x value
-in pass2, for each point, check if the hashmap contains mid-x value or not, if contains, check if they have same y value, if either of condition is not satisfied return false
O(n), O(n)
*/
public static boolean checkReflection2(Point[] points){
if(points==null || points.length<1){
return true;
}
double lowx = Double.MAX_VALUE, highx = Double.MIN_VALUE;
HashMap<Double, HashSet<Double>> map = new HashMap<>();
for(Point p:points){
lowx = Math.min(lowx, p.x);
highx = Math.max(highx, p.x);
map.putIfAbsent(p.x, new HashSet<Double>());
map.get(p.x).add(p.y);
}
double midx = (lowx+highx);//we can store (low+high)/2 but this loses some value and wont find the same key when we search later
//now for each point, check if there is a reflection pair
for(Point p:points){
double refx = Math.abs(p.x - midx);
//if the reflection x with same y-value as p is not found, return false
if(!map.containsKey(refx) || !map.get(refx).contains(p.y)){
return false;
}
}
return true;
}


public static void main(String args[]){
Point[] points = new Point[7];
points[0] = new Point(1,1);
points[1] = new Point(1.5,1);
points[2] = new Point(2.5,1);
points[3] = new Point(3,1);
points[4] = new Point(4,2);
points[5] = new Point(0,2);
points[6] = new Point(0,3);
boolean ref1 = checkReflection1(points);
boolean ref2 = checkReflection2(points);
System.out.println("ref is:"+ref1+"...and:"+ref2);
}
}