Tiles That Form a Rectangle

Hard

You are given a list of rectangular tiles tiles with sides parallel to the axes. A tile [x1, y1, x2, y2] has its bottom-left corner at (x1, y1) and its top-right corner at (x2, y2). Return True if the tiles together cover some rectangle exactly, with no gaps and no overlaps. Otherwise return False.

Example 1

tiles=[[0, 0, 2, 1], [2, 0, 3, 2], [0, 1, 2, 2]] → True

Two 2 × 1 tiles are stacked on the left and a 1 × 2 tile stands on the right: together they make exactly a 3 × 2 rectangle.

Example 2

tiles=[[0, 0, 2, 2], [1, 0, 3, 2]] → False

The tiles overlap in the strip from x = 1 to x = 2.

Example 3

tiles=[[0, 0, 1, 1], [2, 0, 3, 1]] → False

A gap remains between the tiles, so they do not form a rectangle.

Constraints

1 ≤ len(tiles) ≤ 2·10⁴
len(tiles[i]) = 4
-10⁵ ≤ x1 < x2 ≤ 10⁵
-10⁵ ≤ y1 < y2 ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Line Sweep

Similar problems

City Block Outline Hard Area Covered by Overlapping Rectangles Hard The Narrowest Range Around Each Point Hard Halve the Covered Area Hard Overlap of Two Schedules Medium

Input

tiles=[[0, 0, 2, 1], [2, 0, 3, 2], [0, 1, 2, 2]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 92 tests on the server, hidden ones included.