Check if Grid can be Cut into Sections

An n by n grid contains non-overlapping rectangles. Each entry [startX, startY, endX, endY] in rectangles gives a rectangle's bottom-left and top-right corners.

Determine whether two horizontal cuts or two vertical cuts can divide the grid into three sections such that every section contains at least one rectangle and no rectangle is split between sections. Both cuts must have the same direction. A cut may lie along a rectangle's boundary, but it must not pass through its interior.

Return true if such cuts exist, and false otherwise.

Example 1:

Check if Grid can be Cut into Sections, example 1: illustration of the example

Input: n = 3
rectangles = [[0,0,1,3],[1,0,2,3],[2,0,3,3]]

Output: true

Explanation: Vertical cuts at x = 1 and x = 2 create three strips, each containing one rectangle. The cuts follow rectangle boundaries and split no rectangle.

Example 2:

Check if Grid can be Cut into Sections, example 2: illustration of the example

Input: n = 3
rectangles = [[0,0,3,1],[0,1,3,2],[0,2,3,3]]

Output: true

Explanation: Horizontal cuts at y = 1 and y = 2 create three strips with one rectangle each. Cutting along a shared boundary is allowed.

Example 3:

Check if Grid can be Cut into Sections, example 3: illustration of the example

Input: n = 3
rectangles = [[0,0,2,1],[2,0,3,1],[0,1,1,3],[1,1,3,3]]

Output: false

Explanation: The rectangle from x = 0 to x = 2 blocks a vertical cut at x = 1, and the rectangle from x = 1 to x = 3 blocks one at x = 2. Horizontally, only y = 1 separates rectangles, so there are not two valid cuts.

Constraints:

3 <= n <= 1000000000
3 <= rectangles.length <= 100000
Each rectangle is [startX, startY, endX, endY].
0 <= startX < endX <= n
0 <= startY < endY <= n
Rectangle interiors do not overlap.

Topics

Array Sorting

Company Tags

Please upgrade to NeetCode Pro to view company tags.