Simple java hashset solution


  • 59
    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?


  • -6

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


  • 5
    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?


  • 0
    H

    @xxxxxxxxxxy Probably we could override hashCode() like:

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
    

    so that collision would be eliminated.


Log in to reply
 

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