# Short corner xor solution

• ``````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...

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

• 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.

• @livelearn Why the "*m"?

• 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)

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

• @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))

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

• @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

• @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
``````

• 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

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

``````>>> import dis
>>> dis.dis(compile('s ^= t', '', 'exec'))
6 INPLACE_XOR
7 STORE_NAME               0 (s)
13 RETURN_VALUE
>>> dis.dis(compile('s = s ^ t', '', 'exec'))