(Leetcode) Perfect Rectangle

Question

This is a Leetcode problem -

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

Answer 1

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