Check if Grid can be Cut into Sections solution and explanation
Google
9 more videos on this problem
Check if Grid can be Cut into Sections | Merge Intervals | Leetcode 3394 | Leetcode 56 | DetailedcodestorywithMIK · 43:18 · 14K views
Check if Grid can be Cut into Sections - Leetcode 3394 - PythonNeetCodeIO · 13:00 · 9K views
Check if Grid can be Cut into Sections | Leetcode 3394Techdose · 24:37 · 4K views
3394. Check if Grid can be Cut into Sections | Merge Intervals | Line Sweep | Arrays | SortingAryan Mittal · 18:38 · 3K views
3394. Check if Grid can be Cut into Sections || LeetcodePrateek Goel · 7:54 · 483 views
Check if Grid can be Cut into Sections | Leetcode 3394 | Daily Question | Merge IntervalsAbhinav Bansal · 12:58 · 422 views
Daily Leetcode #1820: Mar 25, 2025 - 3394. Check if Grid can be Cut into SectionsProgramming Live with Larry · 18:19 · 304 views
Check if Grid can be Cut into Sections Leetcode 3394R Sai Siddhu · 9:56 · 246 views
3394. Check if Grid can be Cut into Sections (Leetcode Medium)Programming Live with Larry · 12:11 · 206 views
3394. Check if Grid Can Be Cut into Sections | Leetcode Python Solution | Greedy + SortingStatLearn Tech · 16:40 · 108 views
The problem
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:
- Each of the three resulting sections formed by the cuts contains at least one rectangle.
- Every rectangle belongs to exactly one section.
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] <= n- No two rectangles overlap.
Approach overview
Problem 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.
Solution
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)class Solution {
// Helper class to mimic C++ pair<int, int>
static class Pair {
int value;
int type;
Pair(int value, int type) {
this.value = value;
this.type = type;
}
}
private boolean countLineIntersections(List<Pair> coordinates) {
int lines = 0;
int overlap = 0;
for (Pair coord : coordinates) {
if (coord.type == 0) {
overlap--;
} else {
overlap++;
}
if (overlap == 0) {
lines++;
}
}
return lines >= 3;
}
public boolean checkValidCuts(int n, int[][] rectangles) {
List<Pair> yCoordinates = new ArrayList<>();
List<Pair> xCoordinates = new ArrayList<>();
for (int[] rectangle : rectangles) {
// rectangle = [x1, y1, x2, y2]
yCoordinates.add(new Pair(rectangle[1], 1)); // y1, start
yCoordinates.add(new Pair(rectangle[3], 0)); // y2, end
xCoordinates.add(new Pair(rectangle[0], 1)); // x1, start
xCoordinates.add(new Pair(rectangle[2], 0)); // x2, end
}
Comparator<Pair> comparator = (a, b) -> {
if (a.value != b.value) return Integer.compare(a.value, b.value);
return Integer.compare(a.type, b.type); // End (0) before Start (1)
};
Collections.sort(yCoordinates, comparator);
Collections.sort(xCoordinates, comparator);
return countLineIntersections(yCoordinates) || countLineIntersections(xCoordinates);
}
}class Solution {
#define pii pair<int, int>
bool countLineIntersections(vector<pii>& coordinates) {
int lines = 0;
int overlap = 0;
for (int i = 0; i < coordinates.size(); ++i) {
if (coordinates[i].second == 0)
overlap--;
else
overlap++;
if (overlap == 0)
lines++;
}
return lines >= 3;
}
public:
bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
vector<pii> y_cordinates, x_cordinates;
for (auto& rectangle : rectangles) {
y_cordinates.push_back(make_pair(rectangle[1], 1));
y_cordinates.push_back(make_pair(rectangle[3], 0));
x_cordinates.push_back(make_pair(rectangle[0], 1));
x_cordinates.push_back(make_pair(rectangle[2], 0));
}
sort(y_cordinates.begin(), y_cordinates.end());
sort(x_cordinates.begin(), x_cordinates.end());
// Line-Sweep on x and y cordinates
return (countLineIntersections(y_cordinates) or countLineIntersections(x_cordinates));
}
};function checkValidCuts(n, rectangles) {
const check = (arr, getVals) => {
let [c, longest] = [3, 0];
for (const x of arr) {
const [start, end] = getVals(x);
if (start < longest) {
longest = Math.max(longest, end);
} else {
longest = end;
if (--c === 0) return true;
}
}
return false;
};
const sortByX = ([a], [b]) => a - b;
const sortByY = ([, a], [, b]) => a - b;
const getX = ([x1, , x2]) => [x1, x2];
const getY = ([, y1, , y2]) => [y1, y2];
return check(rectangles.toSorted(sortByX), getX) || check(rectangles.toSorted(sortByY), getY);
}function checkValidCuts(n: number, rectangles: number[][]): boolean {
const check = (arr: number[][], getVals: (x: number[]) => number[]) => {
let [c, longest] = [3, 0];
for (const x of arr) {
const [start, end] = getVals(x);
if (start < longest) {
longest = Math.max(longest, end);
} else {
longest = end;
if (--c === 0) return true;
}
}
return false;
};
const sortByX = ([a]: number[], [b]: number[]) => a - b;
const sortByY = ([, a]: number[], [, b]: number[]) => a - b;
const getX = ([x1, , x2]: number[]) => [x1, x2];
const getY = ([, y1, , y2]: number[]) => [y1, y2];
return check(rectangles.toSorted(sortByX), getX) || check(rectangles.toSorted(sortByY), getY);
}type Pair struct {
val int
typ int // 1 = start, 0 = end
}
func countLineIntersections(coords []Pair) bool {
lines := 0
overlap := 0
for _, p := range coords {
if p.typ == 0 {
overlap--
} else {
overlap++
}
if overlap == 0 {
lines++
}
}
return lines >= 3
}
func checkValidCuts(n int, rectangles [][]int) bool {
var xCoords []Pair
var yCoords []Pair
for _, rect := range rectangles {
x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]
yCoords = append(yCoords, Pair{y1, 1}) // start
yCoords = append(yCoords, Pair{y2, 0}) // end
xCoords = append(xCoords, Pair{x1, 1})
xCoords = append(xCoords, Pair{x2, 0})
}
sort.Slice(yCoords, func(i, j int) bool {
if yCoords[i].val == yCoords[j].val {
return yCoords[i].typ < yCoords[j].typ // end before start
}
return yCoords[i].val < yCoords[j].val
})
sort.Slice(xCoords, func(i, j int) bool {
if xCoords[i].val == xCoords[j].val {
return xCoords[i].typ < xCoords[j].typ
}
return xCoords[i].val < xCoords[j].val
})
return countLineIntersections(yCoords) || countLineIntersections(xCoords)
}Complexity analysis
| 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 |
Frequently asked questions
Is Check if Grid can be Cut into Sections easy or hard?
The problem is rated Medium because the implementation is simple once you recognize the interval insight. The main challenge is realizing that valid cuts must lie between non-overlapping rectangle groups rather than testing every grid coordinate.
Check if Grid can be Cut into Sections Python/Java solution
Implement the interval approach: extract x-intervals and y-intervals from the rectangles, sort them, merge overlaps, and count disjoint segments. If either axis produces three or more segments, return true. This logic is straightforward to implement in Python, Java, C++, or JavaScript using standard sorting functions.
How to solve Check if Grid can be Cut into Sections in O(n log n)?
Project each rectangle to intervals along one axis, such as [x1, x2] for vertical cuts. Sort intervals by their start coordinate and merge overlaps while counting disjoint groups. If you find at least three non-overlapping groups, two cuts can be placed between them. Repeat the same process with y-intervals to check horizontal cuts.
What is the best approach for Check if Grid can be Cut into Sections?
The most efficient approach converts rectangles into intervals and sorts them. Project rectangles onto the x-axis and y-axis, merge overlapping intervals, and count how many disjoint groups remain. If at least three groups exist along either axis, two valid cuts can be placed between them. This runs in O(n log n) time due to sorting.
Is Check if Grid can be Cut into Sections asked at Google/Amazon/Meta?
Interval merging and geometric partitioning problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying pattern of sorting intervals and detecting gaps is a common interview topic.
What data structure is used in Check if Grid can be Cut into Sections?
The solution mainly uses arrays or lists to store rectangle intervals. After sorting these intervals, a simple linear scan merges overlapping ranges and counts groups. No advanced data structures are required beyond sorting and basic array traversal.
What is the time complexity of Check if Grid can be Cut into Sections?
The optimal solution runs in O(n log n) time and O(n) space. Sorting the rectangle intervals dominates the runtime, while the merge scan itself is linear. A naive brute-force approach that tries all possible cut pairs can degrade to around O(n^2).