11ms two-pass HashSet-based Java Solution


  • 19
    F

    The idea is quite simple. If there exists a line reflecting the points, then each pair of symmetric points will have their x coordinates adding up to the same value, including the pair with the maximum and minimum x coordinates. So, in the first pass, I iterate through the array, adding each point to the hash set, and keeping record of the minimum and maximum x coordinates. Then, in the second pass, I check for every point to the left of the reflecting line, if its symmetric point is in the point set or not. If all points pass the test, then there exists a reflecting line. Otherwise, not.

    By the way, here, to hash the content of an array, rather than the reference value, I use Arrays.hashCode(int[]) first, and then re-hash this hash code. You can also use Arrays.toString(int[]) to first convey the 2d array to a string, and then hash the string. But the second method is slower.

    public class Solution {
        public boolean isReflected(int[][] points) {
            HashSet<Integer> pointSet = new HashSet<>();
            int sum;
            int maxX, minX;
            
            minX = Integer.MAX_VALUE;
            maxX = Integer.MIN_VALUE;
            for(int[] point:points) {
                maxX = Math.max(maxX, point[ 0 ]);
                minX = Math.min(minX, point[ 0 ]);
                pointSet.add(Arrays.hashCode(point));
            }
            
            sum = maxX+minX;
            for(int[] point:points) {
                if(!pointSet.contains(Arrays.hashCode(new int[]{sum-point[ 0 ], point[ 1 ]}))) {
                    return false;
                }
            }
            return true;
        }
    }

  • 0
    J

    if(point[ 0 ]<sum-point[ 0 ] && !pointSet.contains(Arrays.hashCode(new int[]{sum-point[ 0 ], point[ 1 ]}))) {
    the first condition should be deleted;like:
    if( !pointSet.contains(Arrays.hashCode(new int[]{sum-point[ 0 ], point[ 1 ]}){

    you can test [[1,1],[9,1],[8,2]], your result will be true,but the answer should be false;


  • 0
    F

    Thank you! You are right. I probably shouldn't have this limit: point[ 0 ]<sum-point[ 0 ].
    I've modified my code. Thanks again!


  • 0
    L
    This post is deleted!

  • 0
    F

    Yes, you are absolutely right. But given a relatively small test case, we may assume that they have different hash codes. Otherwise, any problem solvable by hash tables in leetcode will require an additional check, to see if the two objects are actually the same or not. But still, it's more rigid to do that additional check.


  • 0
    L
    This post is deleted!

  • 1
    F

    Thanks, you are right, it's not safe to use hashcode here. Then how about coverting to a string first, and then hashing that string?


  • 0
    C

    Overflow could happen, better use long for sum


  • 0
    J

    just use string to solve it ,very simple!
    https://leetcode.com/discuss/108319/simple-java-hashset-solution


  • 0
    F

    Yes, you are right! Details matter!


  • 0
    L

    what if there are duplicate points?
    such as (-1,0), (-1,0), (1, 0)


  • 0
    F

    I am not sure if the definition of the problem covers this case. But if you run this as your custom test case, I think the expected answer will be 'true'


  • 0

    Definitely the simplest solution. May overflow if provided with a big array.


  • 0
    R

    @Fanchao said in 11ms two-pass HashSet-based Java Solution:

    then each pair of symmetric points will have their x coordinates adding up to the same value

    I don't understand what this means, why each pair of symmetric points have their x coord adding up to the same value? A counter example below:

    {1, 1}, {3, 1}    // 1 + 3 = 4
    {2, 1}, {4, 1}   // 2 + 4 = 6
    

    Could you explain it? thanks


  • 0

    @rcholic The question asks to find a line that reflects all the points


  • 0
    S

    @OpMaker Would you mind explaining this a little more, even I am not able to understand the difference between reflecting individual pair of points across the line and allpoints across line. Thank you for your help.

          o-----------|------------o
               o------|-------o
    

    I had this kind of imagination where the vertical line is reflecting all points on the left to right. I dont know how their x values sum to same total.


  • 1

    @swatisaoji1 Your imagination is correct.
    So let's say the points in your picture is
    n1, n2
    n3, n4
    corresponding to points' positions in your delineation, and suppose the line's x coordinate is k
    Then shouldn't it be (x1+x2)/2=k, and (x3+x4)/2=k as well? And for all points n with coordinate (Xn, Yn), it should satisfy (Xn+Yn)/2=k, if there exists a line that can reflect all the points.


  • 0
    S

    @OpMaker Thanks for the reply, now it makes more sense :

    @rcholic said in 11ms two-pass HashSet-based Java Solution:

    @Fanchao said in 11ms two-pass HashSet-based Java Solution:

    then each pair of symmetric points will have their x coordinates adding up to the same value

    I don't understand what this means, why each pair of symmetric points have their x coord adding up to the same value? A counter example below:

    {1, 1}, {3, 1}    // 1 + 3 = 4
    {2, 1}, {4, 1}   // 2 + 4 = 6
    

    Could you explain it? thanks

    @OpMaker I now understand what you suggest.
    and if we take @rcholic 's points the pair formed are

      { 1, 1} and  { 4, 1}  x1 + x2 = 5 
      { 2, 1}  and { 3, 1}  x3 + x4 = 5
    
    and the reflecting line is at x = 2.5

  • 0

    Using hashcode is not safe.


Log in to reply
 

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