Watch 10 video solutions for Check if Grid can be Cut into Sections, a medium level problem involving Array, Sorting. This walkthrough by codestorywithMIK has 13,126 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer n representing the dimensions of an n x n grid, with the origin at the bottom-left corner of the grid. You are also given a 2D array of coordinates rectangles, where rectangles[i] is in the form [startx, starty, endx, endy], representing a rectangle on the grid. Each rectangle is defined as follows:
(startx, starty): The bottom-left corner of the rectangle.(endx, endy): 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:
Return true if such cuts can be made; otherwise, return false.
Example 1:
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 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
Explanation:
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
Explanation:
We cannot make two horizontal or two vertical cuts that satisfy the conditions. Hence, output is false.
Constraints:
3 <= n <= 1093 <= rectangles.length <= 1050 <= rectangles[i][0] < rectangles[i][2] <= n0 <= rectangles[i][1] < rectangles[i][3] <= nProblem Overview: You are given multiple rectangles inside a grid. The task is to check whether two parallel cuts (either vertical or horizontal) can divide the grid into three sections such that each section contains at least one rectangle and no rectangle is intersected by a cut.
Approach 1: Brute Force Cut Simulation (O(n^2) time, O(1) space)
Try every possible pair of vertical cuts and every pair of horizontal cuts. For each candidate pair, iterate through all rectangles and verify whether every rectangle lies completely inside one of the three resulting sections. If a rectangle crosses a cut, the pair is invalid. This approach works conceptually but becomes slow because each candidate cut pair requires scanning all rectangles. It is mainly useful for reasoning about the problem constraints.
Approach 2: Interval Grouping with Sorting (O(n log n) time, O(n) space)
Instead of testing every cut location, observe that a valid cut must lie in the gap between rectangles. Project each rectangle onto one axis and treat it as an interval. For vertical cuts, use the x intervals [x1, x2]. Sort intervals by start coordinate and merge overlapping ones. Each merged block represents a continuous region where a cut cannot pass.
If the merged intervals form at least three disjoint groups, two cuts can be placed between these groups. The same process is repeated for the y intervals to check horizontal cuts. Sorting the intervals dominates the runtime, giving O(n log n) time with O(n) space for storing intervals.
This method relies on classic interval processing techniques from sorting and array scanning patterns from arrays. Instead of simulating cuts directly, you detect safe gaps where cuts can exist.
Recommended for interviews: The sorting + interval grouping approach is what interviewers expect. Brute force shows that you understand the geometric constraints, but the optimized method demonstrates the ability to transform the grid problem into interval merging using sorting. That reduction is the key insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Cut Simulation | O(n^2) | O(1) | Conceptual baseline or very small inputs |
| Sorting + Interval Grouping | O(n log n) | O(n) | General case; efficient for large number of rectangles |