NeetCode #843LC-3394MediumIntervals
← Back to All Problems#843 · #3394 · Check if Grid can be Cut into Sections(判断网格图能否被切割成块)
📌 Problem Statement & Constraints
You are given an integer
n and a 2D array rectangles where rectangles[i] = [x1, y1, x2, y2] is an axis-aligned rectangle inside an n x n grid. Return true if you can make either two horizontal cuts or two vertical cuts that split the grid into three sections, each containing at least one rectangle, without cutting through any rectangle. Constraints: 3 <= n <= 10^9, 3 <= rectangles.length <= 10^5, 0 <= x1 < x2 <= n, 0 <= y1 < y2 <= n.💡 Core Algorithmic Approaches
- A vertical cut is valid at position
cif no rectangle spans across it, i.e. no rectangle hasx1 < c < x2. - Project the rectangles onto the x-axis as half-open intervals
[x1, x2)and merge them; each merged gap is a place where a cut can pass. - Two vertical cuts give three sections only if the merged x-intervals split into at least three groups.
- The same test on the y-intervals handles horizontal cuts; either succeeding is enough.
💻 Benchmark Python3 Implementation
class Solution:
def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
def can_cut(intervals: List[List[int]]) -> bool:
intervals.sort()
groups = 0
cur_end = -1
for s, e in intervals:
if s >= cur_end: # a gap exists -> a new group starts
groups += 1
cur_end = e
else:
cur_end = max(cur_end, e)
return groups >= 3
x = [[r[0], r[2]] for r in rectangles]
y = [[r[1], r[3]] for r in rectangles]
return can_cut(x) or can_cut(y)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the projections dominates.
💾 Space Complexity
O(n): the two projection arrays.
⚠️ Interview Pitfalls & Follow-ups
- Treating the rectangles as closed intervals: a cut exactly at
x2of one rectangle andx1of the next is legal, so the intervals are half-open and the test iss >= cur_end. - Requiring exactly three groups: more groups also work, since two cuts can always pick two of the gaps, so the condition is
>= 3. - Checking only one orientation: the problem allows either two horizontal or two vertical cuts, so both projections must be tested.
- Assuming the rectangles are disjoint: they can overlap arbitrarily; the merge handles that correctly.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.