Simple Java Solution, O(n), HashMap


  • 0
    L

    "1. Find the smallest and largest x-value for all points.
    If there is a line then it should be at y = (minX + maxX) / 2"

    Also, we know that reflected points shall have the same Y.
    Then, we store all Xs in a Set that have the same Y value.
    For the set of Xs that have the same Y, we verify for any x, we have a (y - X) in the set. If not, then return false.
    Big O = O(n), n == points.size.

    public boolean isReflected(int[][] points) {
            //Y is key, value is all the Xs. 
            HashMap<Integer, HashSet<Integer>> yToXsMap = new HashMap<>();
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for(int[] p : points){
            	HashSet<Integer> xSets = yToXsMap.getOrDefault(p[1], new HashSet<Integer>());
            	xSets.add(p[0]);
            	yToXsMap.put(p[1], xSets);
            	max = Math.max(max, p[0]);
            	min = Math.min(min, p[0]);
            }
            int judge = max + min;//any reflected points A(x, y), B(x', y) shall satisfy that x + x' == judge. 
            for(HashSet<Integer> xSets: yToXsMap.values()){
            	//if(xSets.size() % 2 != 0) return false;//special case: [(0, 0)]
            	for(Integer x : xSets){
            	    //there should be a point whose x' == judge - x.
            		if(!xSets.contains(judge - x)) return false;
            	}
            }
            return true;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.