3
\$\begingroup\$

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.

enter image description here

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.

enter image description here

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.

enter image description here

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.

enter image description here

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 -

enter image description here

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

Any help would be highly appreciated.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Unrelated, but hope this may help you. You can see the fastest solution codes on leetcode (only works if you have an accepted submission) by going to the problem, clicking submissions, clicking accepted, and then clicking on the furthest bar to the left of the graph \$\endgroup\$ Commented Jun 7, 2019 at 20:16

1 Answer 1

Reset to default
3
\$\begingroup\$

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()
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.