Problem

This is a Leetcode problem –

Given N$N$ axis-aligned rectangles where N$N$ >$>$`0`

, determine if

they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right

point. For example, a unit square is represented as`[1, 1, 2, 2]`

.

(coordinate of the bottom-left point is`(1, 1)`

and the top-right

point is`(2, 2)`

).

Example 1 –

`rectangles = [ [1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4] ] # Explanation - Return True. All 5 rectangles together form an exact cover of a rectangular region.`

Example 2 –

`rectangles = [ [1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2], [3, 2, 4, 4] ] # Explanation - Return False. Because there is a gap between the two rectangular regions.`

Example 3 –

`rectangles = [ [1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4] ] # Explanation - Return False. Because there is a gap in the top center.`

Example 4 –

`rectangles = [ [1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4] ] # Explanation - Return False. Because two of the rectangles overlap with each other.`

Here is my solution to this challenge –

```
def is_rectangle_cover(rectangles):
if len(rectangles) == 0 or len(rectangles[0]) == 0:
return False
x1 = float("inf")
y1 = float("inf")
x2 = 0
y2 = 0
rect = set()
area = 0
for points in rectangles:
x1 = min(points[0], x1)
y1 = min(points[1], y1)
x2 = max(points[2], x2)
y2 = max(points[3], y2)
area += (points[3] - points[1]) * (points[2] - points[0])
rect.remove((points[0], points[3])) if (points[0], points[3]) in rect else rect.add((points[0], points[3]))
rect.remove((points[0], points[1])) if (points[0], points[1]) in rect else rect.add((points[0], points[1]))
rect.remove((points[2], points[3])) if (points[2], points[3]) in rect else rect.add((points[2], points[3]))
rect.remove((points[2], points[1])) if (points[2], points[1]) in rect else rect.add((points[2], points[1]))
if (x1, y2) not in rect or (x2, y1) not in rect or (x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
return False
return area == (y2 - y1) * (x2 - x1)
```

Here are the times taken for each example output –

*Example 1 –*

```
# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [3, 2, 4, 4], [1, 3, 2, 4], [2, 3, 3, 4]])
14.9 µs ± 117 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
```

*Example 2 –*

```
# %timeit is_rectangle_cover([[1, 1, 2, 3], [1, 3, 2, 4], [3, 1, 4, 2],[3, 2, 4, 4]])
12.5 µs ± 494 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
```

*Example 3 –*

```
# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [3, 2, 4, 4]])
12.4 µs ± 195 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
```

*Example 4 –*

```
# %timeit is_rectangle_cover([[1, 1, 3, 3], [3, 1, 4, 2], [1, 3, 2, 4], [2, 2, 4, 4]])
12 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
```

Here is my Leetcode result for 46 test cases –

Therefore, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Solution

## Use tuples

…instead of lists when your data are immutable. There are a few advantages, including marginal performance increases in some scenarios, and catching “surprises” where code is attempting to modify your data where it shouldn’t.

## Unpack your tuples

Indexing `points`

is nasty.

## Use more sets

I *think* my rewritten code with set operators is equivalent. Peruse the documentation for info on the symmetric difference `^`

and subset `<`

operators.

Edit: you don’t even need the subset test; all you need is set equality.

## Don’t “ternary instead of if”

Even if you didn’t do the symmetric set operation and kept your add/remove code, just… don’t do this. It’s the worst mix of “too clever”, “too illegible” and “difficult to maintain”.

## Coalesce your returns

…into one boolean statement, for simplicity.

## Proposed

```
def is_rectangle_cover_orig(rectangles):
if len(rectangles) == 0 or len(rectangles[0]) == 0:
return False
x1 = float("inf")
y1 = float("inf")
x2 = 0
y2 = 0
rect = set()
area = 0
for points in rectangles:
x1 = min(points[0], x1)
y1 = min(points[1], y1)
x2 = max(points[2], x2)
y2 = max(points[3], y2)
area += (points[3] - points[1]) * (points[2] - points[0])
rect.remove((points[0], points[3])) if (points[0], points[
3]) in rect else rect.add((points[0], points[3]))
rect.remove((points[0], points[1])) if (points[0], points[
1]) in rect else rect.add((points[0], points[1]))
rect.remove((points[2], points[3])) if (points[2], points[
3]) in rect else rect.add((points[2], points[3]))
rect.remove((points[2], points[1])) if (points[2], points[
1]) in rect else rect.add((points[2], points[1]))
if (x1, y2) not in rect or (x2, y1) not in rect or
(x1, y1) not in rect or (x2, y2) not in rect or len(rect) != 4:
return False
return area == (y2 - y1) * (x2 - x1)
def is_rectangle_cover_new(rectangles):
if len(rectangles) == 0 or len(rectangles[0]) == 0:
return False
x1, y1 = float("inf"), float("inf")
x2, y2 = 0, 0
rect = set()
area = 0
for xr1, yr1, xr2, yr2 in rectangles:
x1 = min(xr1, x1)
y1 = min(yr1, y1)
x2 = max(xr2, x2)
y2 = max(yr2, y2)
area += (yr2 - yr1) * (xr2 - xr1)
rect ^= {(xr1, yr2), (xr1, yr1), (xr2, yr2), (xr2, yr1)}
return (
rect == {(x1, y2), (x2, y1), (x1, y1), (x2, y2)} and
area == (y2 - y1) * (x2 - x1)
)
def test():
for i, rects in enumerate((
(
(1, 1, 3, 3),
(3, 1, 4, 2),
(3, 2, 4, 4),
(1, 3, 2, 4),
(2, 3, 3, 4)
),
(
(1, 1, 2, 3),
(1, 3, 2, 4),
(3, 1, 4, 2),
(3, 2, 4, 4)
),
(
(1, 1, 3, 3),
(3, 1, 4, 2),
(1, 3, 2, 4),
(3, 2, 4, 4)
),
(
(1, 1, 3, 3),
(3, 1, 4, 2),
(1, 3, 2, 4),
(2, 2, 4, 4)
)
), 1):
old_ans = is_rectangle_cover_orig(rects)
new_ans = is_rectangle_cover_new(rects)
print(f'Example {i}: {old_ans}')
assert old_ans == new_ans
test()
```