⚡Flashcard Drill➔
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

  1. A vertical cut is valid at position c if no rectangle spans across it, i.e. no rectangle has x1 < c < x2.
  2. 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.
  3. Two vertical cuts give three sections only if the merged x-intervals split into at least three groups.
  4. 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 x2 of one rectangle and x1 of the next is legal, so the intervals are half-open and the test is s >= 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems