1 line Ruby, 2 lines Python


  • 13

    Idea: Reflect the points by replacing every x with minX+maxX-x and then check whether you get the same points. Why minX+maxX-x? I actually thought of it as minX+(maxX-x), i.e., first the subtraction (maxX-x). That's how far x is away from the max, so instead go that distance from the min.


    Update to reflect the changed problem: (Originally, the problem was about a set of points, so no duplicates.)

    def is_reflected(points)
      points.sort!.uniq == points.map { |x, y| [points[0][0] + points[-1][0] - x, y] }.sort.uniq
    end
    
    def isReflected(self, points):
        points = sorted(set(map(tuple, points)))
        return points == sorted((points[0][0] + points[-1][0] - x, y)
                                for x, y in points)
    

    Ruby

    def is_reflected(points)
      points.sort! == points.map { |x, y| [points[0][0] + points[-1][0] - x, y] }.sort
    end
    

    Python

    def isReflected(self, points):
        points.sort()
        return points == sorted([points[0][0] + points[-1][0] - x, y]
                                for x, y in points)
    

    A linear time one:

    def isReflected(self, points):
        if not points: return True
        X = min(points)[0] + max(points)[0]
        return {(x, y) for x, y in points} == {(X - x, y) for x, y in points}
    

    Shorter, but I think less nice:

        return set(map(tuple, points)) == {(X - x, y) for x, y in points}

  • 0
    H

    Can you explain your idea a bit?
    I am not so good at ruby and python


  • 0

    I replace every x with minX+maxX-x and then check whether that gives me the same points.


  • 0
    C

    Since there is a sort I guess the time complexity would be at least O(NlogN) ?


  • 1
    O

    Some explanation to add :P It also took me a while to understand the solution. @StefanPochmann is as magic as always ha.

    The key point is if there is one line to reflects all the points, it must in the middle of maxX and minX.
    Say its at x = (minX + maxX)/2 = m, you can get the reflecting point for any given point on x = n to be at 2m - n = minX + maxX - n

    Therefore, if all points are reflected to each other with this line, the corresponding reflected points set (replace every point with 2m - n) would be exactly the same as the original points set

    Finding maxX and minX, replacing every point to its reflected point, and comparing whether the two sets are the same, are all linear operations.


  • 0

    How did you get 2m - n?

    I actually thought of it as minX + (maxX - x), i.e., first the subtraction (maxX - x). That's how far x is away from the max, so instead go that distance from the min.


  • 0

    This is awesome! I have the same idea but it's much longer.


  • 0
    D

    I don't quiet get when you say :

    Why minX+maxX-x? I actually thought of it as minX+(maxX-x), i.e., first the subtraction (maxX-x)

    Isn't minX+maxX-x the same as minX+(maxX-x)?


  • 0

    @dianhua1560 The result is the same, but the order of the operations differ, and thus the intermediate results differ. And I see the meaning in my intermediate results (see my sentence after it) but not in chungyushao's.


  • 0
    D

    @StefanPochmann So the purpose is to illustrate the meaning of this statement? and maybe to avoid overflow?


  • 0

    @dianhua1560 Yes, to show how I think of it, what it means to me. No, not because of overflow, as the numbers are integers and neither Ruby nor Python have integer overflows.


  • 0
    D

    @StefanPochmann Got it. Thanks for your replies!


  • 0
    D

    thx. !! I like the idea that checking the distance from sum of x1 and x2 rather than finding the middle line.


  • 0
    D

    Hmm..

    This solution failed with this case.
    Input:
    [[-16,1],[16,1],[16,1]]
    Output:
    false
    Expected:
    true


    minX = -16
    maxX = 16
    minX+maxX = 0
    and it becomes [16, 1], [-16, 1], [-16, 1]


    the duplicated points make problem


  • 1

    @DPpanic Yeah, originally, the problem was about a set of points, so no duplicates. Then someone ignored that and duplicates got added and the problem changed. I guess I should adapt my solutions or add a note...


  • 0
    D

    @StefanPochmann got it. I agree with you. it needs some memo saying that there could be dups in points.


  • 0
    W
    This post is deleted!

  • 0
    W

    Awesome solution, are the time and space complexity both O(N) ?


Log in to reply
 

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