#3394

Medium

LeetCode Problem Workspace

Check if Grid can be Cut into Sections

Determine if an n x n grid can be divided with two horizontal or vertical cuts using rectangle ranges efficiently.

Problem Statement

You are given an integer n representing an n x n grid, with coordinates starting from the bottom-left. A list of non-overlapping rectangles is provided, each defined by [startx, starty, endx, endy]. Each rectangle covers all points from its start coordinates up to but not including its end coordinates.

Your task is to determine if it is possible to make exactly two horizontal or two vertical cuts such that each resulting section contains one or more rectangles entirely within it. Return true if such cuts exist, otherwise return false.

Examples

Example 1

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

Output: true

The grid is shown in the diagram. We can make horizontal cuts at y = 2 and y = 4 . Hence, 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

We can make vertical cuts at x = 2 and x = 3 . Hence, output is true.

Example 3

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

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

Constraints

3 <= n <= 109
3 <= rectangles.length <= 105
0 <= rectangles[i][0] < rectangles[i][2] <= n
0 <= rectangles[i][1] < rectangles[i][3] <= n
No two rectangles overlap.

Solution Approach

Separate and Sort Coordinates

Extract all x and y ranges from the rectangles. Sort start and end coordinates independently to efficiently analyze potential horizontal and vertical cut positions.

Identify Valid Cut Positions

Check sorted ranges to find gaps between rectangles that could serve as cut lines. Ensure that two non-overlapping cuts fully divide the grid sections as required by the problem.

Validate and Return Result

If two valid horizontal cuts or two valid vertical cuts are identified that separate rectangles correctly, return true. Otherwise, return false. This approach prevents missed edge cases due to unsorted or overlapping ranges.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(S)

Sorting the rectangle start and end coordinates dominates the runtime with O(n \log n). Space complexity O(S) accounts for storing the coordinates and temporary arrays used for gap analysis.

What Interviewers Usually Probe

Notice if candidate separates x and y coordinates instead of treating rectangles as full objects.
Look for the candidate using sorting to quickly identify potential cuts.
Pay attention to whether the candidate considers gaps between rectangles rather than individual points.

Common Pitfalls or Variants

Common pitfalls

Failing to sort coordinates before checking for gaps can miss valid cut positions.
Assuming overlapping rectangles might exist despite the constraint forbidding it.
Checking only horizontal or only vertical cuts without considering both possibilities.

Follow-up variants

Determine if exactly three cuts can divide the grid into four valid sections.
Consider rectangles that may partially overlap and find maximal non-overlapping cuts.
Optimize for minimal total number of cuts needed to separate all rectangles.

FAQ

What pattern is most important for 'Check if Grid can be Cut into Sections'?

The Array plus Sorting pattern is key: sort rectangle start and end coordinates to find valid cut positions efficiently.

Can this approach handle very large n and many rectangles?

Yes, sorting and gap detection ensures O(n \log n) time, suitable for grids up to 10^9 and up to 10^5 rectangles.

Why do we analyze x and y ranges separately?

Separating ranges prevents missing potential horizontal or vertical cuts and simplifies gap detection between rectangles.

Is it enough to check only horizontal cuts?

No, both horizontal and vertical cuts must be considered to satisfy the problem's requirements.

What is a common failure mode when solving this problem?

A common failure is ignoring the sorting step, which can cause missed cut positions and incorrect false results.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

class Solution:
    def countLineIntersections(self, coordinates: List[tuple[int, int]]) -> bool:
        lines = 0
        overlap = 0
        for value, marker in coordinates:
            if marker == 0:
                overlap -= 1
            else:
                overlap += 1

            if overlap == 0:
                lines += 1

        return lines >= 3

    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
        y_coordinates = []
        x_coordinates = []

        for rect in rectangles:
            x1, y1, x2, y2 = rect
            y_coordinates.append((y1, 1))  # start
            y_coordinates.append((y2, 0))  # end

            x_coordinates.append((x1, 1))  # start
            x_coordinates.append((x2, 0))  # end

        # Sort by coordinate value, and for tie, put end (0) before start (1)
        y_coordinates.sort(key=lambda x: (x[0], x[1]))
        x_coordinates.sort(key=lambda x: (x[0], x[1]))

        return self.countLineIntersections(
            y_coordinates
        ) or self.countLineIntersections(x_coordinates)

Continue Practicing

#3397 maximum number of distinct elements after operations #3382 maximum area rectangle with point constraints ii #3380 maximum area rectangle with point constraints i