Short corner xor solution


  • 1
    def isRectangleCover(self, rectangles):
        area = 0
        corners = set()
        a, c = lambda: (X - x) * (Y - y), lambda: {(x, y), (x, Y), (X, y), (X, Y)}
        for x, y, X, Y in rectangles:
            area += a()
            corners ^= c()
        x, y, X, Y = (f(z) for f, z in zip((min, min, max, max), zip(*rectangles)))
        return area == a() and corners == c()
    

    Equivalent to what others have done, just relatively short. I check that the sum of areas matches the rectangular hull's area and that the corners appearing an odd number of times are exactly the hull's corners. I have a rough idea for a proof, might try finishing it later...


  • 0
    L

    Had no idea that set has a xor shortcut for the symmetric difference command.


  • 0
    L

    Also curious as to the run time of this? It looks like it is O(n*m) where n is the length of rectangles and m is the length of corners. Might not be the most efficient solution.


  • 0

    @livelearn Why the "*m"?


  • 0
    L

    Well the m could be huge in a case if none of the rectangles overlapped...maybe something like [[1,1,2,2],[3,3,4,4],[5,5,6,6],[7,7,8,8],[9,9,10,10]].

    Wouldn't it make more sense to use the theoretical O(1) times of remove and add for set?

    for x in nums:
            for p in c():
                if p in corners:
                    corners.remove(p)
                else: corners.add(p)

  • 0

    @livelearn What makes you think it isn't doing something like that remove/add?


  • 0
    L

    @StefanPochmann
    "new set with elements in either s or t but not both"
    So it seems like s ^ t is equivalent to O(len(s)+len(t))


  • 0

    @livelearn I didn't say that. Where is that quote from? More importantly, I'm not using ^. I'm using ^=.


  • 0
    L

    @StefanPochmann You can find it here https://docs.python.org/2/library/sets.html. I would assume that the s^=t is equivalent to s=s^t


  • 1

    @livelearn You assume wrong. The s = s ^ t uses the s.__xor__ method to compute a new set and then assigns it, while the s ^= t uses the s.__ixor__ method to just modify the set.

    Compare:

    >>> s = t = {1, 2, 3}
    >>> s ^= {2, 4}
    >>> t
    set([1, 3, 4])
    
    >>> s = t = {1, 2, 3}
    >>> s = s ^ {2, 4}
    >>> t
    set([1, 2, 3])
    

    And some timings:

    >>> from timeit import timeit
    >>> timeit('s ^= x',    's = set(range(1000)); x = {42}')
    0.07867587826531652
    >>> timeit('s = s ^ x', 's = set(range(1000)); x = {42}')
    16.825787989205928
    

  • 0
    L

    Wow, truly amazing. I was looking for something similar to the x__ixor__ method, but couldn't find anything. Might have to check the source code. Surprised your answer doesn't have more upvotes


  • 1

    @livelearn Just another way to see the difference, showing the more meaningful name "INPLACE_XOR":

    >>> import dis
    >>> dis.dis(compile('s ^= t', '', 'exec'))
      1           0 LOAD_NAME                0 (s)
                  3 LOAD_NAME                1 (t)
                  6 INPLACE_XOR         
                  7 STORE_NAME               0 (s)
                 10 LOAD_CONST               0 (None)
                 13 RETURN_VALUE        
    >>> dis.dis(compile('s = s ^ t', '', 'exec'))
      1           0 LOAD_NAME                0 (s)
                  3 LOAD_NAME                1 (t)
                  6 BINARY_XOR          
                  7 STORE_NAME               0 (s)
                 10 LOAD_CONST               0 (None)
                 13 RETURN_VALUE        
    

  • 0
    L

    @StefanPochmann WOW! Now I can actually dissemble python code, see the instructions within the bytecode. This is so useful, I'm surprised I've never seen it being mentioned.


Log in to reply
 

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