Simple java hashset solution


  • 58
    J
       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;
    }

  • 0
    G

    Smart solution!


  • 0
    M

    Very clean and easy understanding!

    May I ask what is the time and space complexity of your solution?


  • -5

    The way you use String to encode a integer pair is strange.


  • 4
    X

    Same solution without using the String trick.

    public class Solution {
        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;
                set.add(new Point(point[0], point[1]));
            }
            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;
            }
        }
    }
    

  • 0

    Encoding array hashcode to string is awesome.


  • 1
    A

    @MintMen the hashCode method in Point class may introduce collisions, though possibility is low. Not sure what can be done here to override the hashCode method during an interview


  • 0
    Z

    @a08805436 Maybe we still need to overwrite the hashCode() like what @juanren did to avoid conflict..


  • 4
    W

    @juanren The test cases do not have duplicated points. If they have, your code cannot handle them.


  • 0

    @juanren clean solution! Did you consider java.awt.Point instead of String? thanks


  • 0

    @whoops said in Simple java hashset solution:

    @juanren The test cases do not have duplicated points. If they have, your code cannot handle them.

    The test cases do have duplicate points, e.g. [[-16,1],[16,1],[16,1]], and the result should return true in this case.

    Dups didn't crash the code, since HashSet simply won't insert them.


  • 0
    J

    @zzhai

    in my understanding, duplicate points in the array are duplicate; but in 2D plane, actually they are the same ONE point.


  • 0

    Slightly optimized by replacing string concatenation with long concatenation:

        public boolean isReflected(int[][] points) {
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            
            Map<Integer, Set<Long>> entries = new HashMap<>();
            for (int[] point : points) {
                max = Math.max(max, point[0]);
                min = Math.min(min, point[0]);
                
                entries.computeIfAbsent(point[1], x -> new HashSet<>())
                    .add(keyed(point[0], point[1]));
            }
            
            int end = min + max;
            for (int[] point : points) {
                if (!entries.get(point[1]).contains(keyed(end - point[0], point[1]))) {
                    return false;
                }
            }
            
            return true;
        }
        
        long keyed(long x, long y) {
            return x << 32 | y;
        }
    

  • 0
    J

    Good solution that avoided using a floating type. Even overflow is not a problem


  • 0
    Y

    It looks like the code doesn't work when points overlap, right?

    I did not see the problem mentioned that points can't be overlapped.

    Anyone have any idea?


Log in to reply
 

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