Check if Grid can be Cut into Sections

LeetCode 3394, Medium. Topics: Array, Sorting. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 3394   # by problem number
lcpy gen -s check_if_grid_can_be_cut_into_sections   # by problem name

Problem

You are given an integer <code>n</code> representing the dimensions of an <code>n x n</code> grid, with the origin at the bottom-left corner of the grid. You are also given a 2D array of coordinates <code>rectangles</code>, where <code>rectangles[i]</code> is in the form <code>[startx, starty, endx, endy]</code>, representing a rectangle on the grid. Each rectangle is defined as follows:

<code>(startx, starty)</code>: The bottom-left corner of the rectangle.
<code>(endx, endy)</code>: The top-right corner of the rectangle.

Note that the rectangles do not overlap. Your task is to determine if it is possible to make either two horizontal or two vertical cuts on the grid such that:

Each of the three resulting sections formed by the cuts contains at least one rectangle.
Every rectangle belongs to exactly one section.

Return <code>true</code> if such cuts can be made; otherwise, return <code>false</code>.

Examples

Input: n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
Output: true

Explanation: The grid is shown in the diagram. We can make horizontal cuts at <code>y = 2</code> and <code>y = 4</code>. Hence, the output is true. Example 2

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

Explanation: We can make vertical cuts at <code>x = 2</code> and <code>x = 3</code>. Hence, the output is true.

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

Explanation: We cannot make two horizontal or two vertical cuts that satisfy the conditions. Hence, the output is false.

Constraints

3 <= n <= 10^9
3 <= rectangles.length <= 10^5
0 <= rectangles[i][0] < rectangles[i][2] <= n
0 <= rectangles[i][1] < rectangles[i][3] <= n
No two rectangles overlap.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(m log m)
    # Space: O(m)
    def check_valid_cuts(self, n: int, rectangles: list[list[int]]) -> bool:
        return self._has_two_gaps(rectangles, 0) or self._has_two_gaps(rectangles, 1)

    def _has_two_gaps(self, rectangles: list[list[int]], axis: int) -> bool:
        rects = sorted(rectangles, key=lambda rect: (rect[axis], rect[axis + 2]))
        gaps = 0
        end = rects[0][axis + 2]
        for rect in rects:
            if rect[axis] >= end:
                gaps += 1
                if gaps >= 2:
                    return True
            end = max(end, rect[axis + 2])
        return False

Complexity

Time	Space
O(m log m)	O(m)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Check if Grid can be Cut into Sections

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags