# (Leetcode) Perfect Rectangle

Posted on

Problem

This is a Leetcode problem

Given $$NNN$$ axis-aligned rectangles where $$NNN$$ $$>>>$$ 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.

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

…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()