# Check if Grid can be Cut into Sections
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections)
Canonical: https://scaleengineer.com/dsa/problems/check-if-grid-can-be-cut-into-sections
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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:**

![](https://assets.glich.co/dsa/check-if-grid-can-be-cut-into-sections/image0.png)

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:**

![](https://assets.glich.co/dsa/check-if-grid-can-be-cut-into-sections/image1.png)

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 <= 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.

# Approaches
## Quadratic Approach with Nested Loops
This approach systematically checks all possible ways to partition the sorted rectangles into three contiguous groups. It relies on the observation that if a valid set of cuts exists, the rectangles, when sorted by their coordinates (e.g., `sy` for horizontal cuts), can be divided into three contiguous blocks corresponding to the three sections. We can iterate through all possible pairs of split points `(i, j)` that define these three blocks and check if the geometric separation conditions are met.
**Time:** O(R^2), where R is the number of rectangles. The initial sort takes O(R log R). The nested loops dominate the complexity, running in O(R^2) in the worst case. For each of the O(R) potential first cuts, we might iterate up to O(R) times to find a second cut. · **Space:** O(R), where R is the number of rectangles. This is for storing a copy of the rectangles array and the prefix maximums array.
**Pros:** The logic is straightforward and directly follows from the problem definition.; It's more efficient than a brute-force approach that considers all possible coordinate values for cuts.
**Cons:** The nested loop structure leads to a quadratic time complexity, which is too slow for the given constraints on the number of rectangles (`R <= 10^5`).
### Explanation
The overall strategy is to create a helper function, say `canCut`, that checks if a valid partition is possible for a single orientation (e.g., horizontal). The main function will call this helper for both horizontal and vertical orientations.

The `canCut` function for horizontal cuts works as follows:
1.  Sort the input `rectangles` based on their `sy` (bottom y-coordinate).
2.  Pre-calculate the prefix maximums of the `ey` (top y-coordinate) for the sorted rectangles. Let's call this array `prefixMaxEy`.
3.  Iterate with a loop for the first potential split point, `i`, from `0` to `R-3` (where `R` is the number of rectangles).
4.  Inside the loop, check if a cut between `i` and `i+1` is valid. The condition is `prefixMaxEy[i] < rectangles[i+1].sy`.
5.  If the first cut is valid, start a nested loop for the second potential split point, `j`, from `i+1` to `R-2`.
6.  Inside the inner loop, calculate the maximum `ey` for the middle partition of rectangles from `i+1` to `j`.
7.  Check if the second cut between `j` and `j+1` is valid. The condition is `max_ey_middle < rectangles[j+1].sy`.
8.  If both conditions are met, it means we've found a valid way to make two cuts. Return `true`.
9.  If the loops complete without finding such cuts, return `false`.

The main function `canBeCut` will call `canCut` once for horizontal cuts (sorting by `sy`) and, if that fails, once for vertical cuts (sorting by `sx`).

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean canBeCut(int n, int[][] rectangles) {
        // Check for horizontal cuts
        if (check(rectangles, 1, 3)) {
            return true;
        }
        // Check for vertical cuts
        if (check(rectangles, 0, 2)) {
            return true;
        }
        return false;
    }

    private boolean check(int[][] rectangles, int startDim, int endDim) {
        int R = rectangles.length;
        if (R < 3) {
            return false;
        }

        // Create a copy to avoid modifying the original array across calls
        int[][] rects = new int[R][4];
        for (int i = 0; i < R; i++) {
            rects[i] = Arrays.copyOf(rectangles[i], 4);
        }

        // Sort by the start dimension (sy for horizontal, sx for vertical)
        Arrays.sort(rects, Comparator.comparingInt(r -> r[startDim]));

        // O(R^2) approach
        int[] prefixMaxEnd = new int[R];
        prefixMaxEnd[0] = rects[0][endDim];
        for (int i = 1; i < R; i++) {
            prefixMaxEnd[i] = Math.max(prefixMaxEnd[i - 1], rects[i][endDim]);
        }

        for (int i = 0; i < R - 2; i++) {
            // Check for the first valid cut between i and i+1
            if (prefixMaxEnd[i] < rects[i + 1][startDim]) {
                // If first cut is valid, check for a second valid cut
                int middleMaxEnd = 0;
                for (int j = i + 1; j < R - 1; j++) {
                    middleMaxEnd = Math.max(middleMaxEnd, rects[j][endDim]);
                    if (middleMaxEnd < rects[j + 1][startDim]) {
                        return true; // Found two valid cuts
                    }
                }
            }
        }

        return false;
    }
}
```
### Algorithm
The core idea is to check for horizontal and vertical cuts separately. The logic for both is symmetrical. Let's focus on finding two valid horizontal cuts.

1.  A valid set of two horizontal cuts partitions the rectangles into three non-empty groups: bottom, middle, and top. If we sort the rectangles by their starting y-coordinate (`sy`), these three groups will form three contiguous non-empty subarrays.
2.  Let the sorted rectangles be `r_0, r_1, ..., r_{R-1}` where `R` is the number of rectangles.
3.  We can iterate through all possible split points. Let the first cut be between rectangle `r_i` and `r_{i+1}`, and the second cut be between `r_j` and `r_{j+1}`, where `0 <= i < j < R-1`.
4.  This creates three partitions:
    *   Bottom: `{r_0, ..., r_i}`
    *   Middle: `{r_{i+1}, ..., r_j}`
    *   Top: `{r_{j+1}, ..., r_{R-1}}`
5.  For these partitions to be valid, the cuts must not intersect any rectangles. This means:
    *   The first cut is valid if the highest `ey` in the bottom partition is less than the lowest `sy` in the middle partition. After sorting by `sy`, this simplifies to `max(ey for rects in {0..i}) < r_{i+1}.sy`.
    *   The second cut is valid if the highest `ey` in the middle partition is less than the lowest `sy` in the top partition. This simplifies to `max(ey for rects in {i+1..j}) < r_{j+1}.sy`.
6.  The algorithm iterates through all possible first split points `i` from `0` to `R-3`.
7.  For each `i`, it first checks if a valid cut can be made. This involves computing the maximum `ey` in the prefix `{0..i}`.
8.  If the first cut is valid, it then iterates through all possible second split points `j` from `i+1` to `R-2`.
9.  For each `j`, it checks if the second cut is valid by finding the maximum `ey` in the middle partition `{i+1..j}`.
10. If both cuts are valid, we have found a solution. We return `true`.
11. The entire process is repeated for vertical cuts if no horizontal solution is found. This involves sorting by `sx` and checking `ex` values.

## Optimal Approach with Binary Search and RMQ
This optimized approach avoids the `O(R^2)` complexity by using a more advanced algorithmic technique. After identifying a potential first cut, instead of linearly scanning for a second cut, we use binary search. The feasibility check inside the binary search requires finding the maximum value in a sub-array, which can be answered efficiently using a pre-built Range Maximum Query (RMQ) data structure. This reduces the search for the second cut from `O(R)` to `O(log R)`, leading to a total time complexity of `O(R log R)`.
**Time:** O(R log R), where R is the number of rectangles. The complexity is dominated by sorting the rectangles and building the Sparse Table. The main loop runs R times, and the binary search inside it takes O(log R) with O(1) RMQ queries. · **Space:** O(R log R), where R is the number of rectangles. The space is dominated by the Sparse Table used for Range Maximum Queries.
**Pros:** Highly efficient with a time complexity that scales well for large inputs.; The core logic is sound and guaranteed to find a solution if one exists.
**Cons:** The implementation is more complex due to the need for a Range Maximum Query data structure (like a Sparse Table or Segment Tree) and binary search.
### Explanation
The `canCut` helper function is modified to be more efficient.

1.  Sort the rectangles based on their `sy` coordinate.
2.  Build a Sparse Table for Range Maximum Queries on the `ey` coordinates. The build process takes `O(R log R)` time.
3.  Pre-calculate the prefix maximums of `ey` in an array `prefixMaxEy` in `O(R)` time.
4.  Iterate with a loop for the first potential split point, `i`, from `0` to `R-3`.
5.  Check if the first cut is valid: `prefixMaxEy[i] < rectangles[i+1].sy`. This is an `O(1)` check.
6.  If the first cut is valid, perform a binary search on the range `[i+1, R-2]` to find a valid second split point `j`.
7.  In the binary search, for a given `mid_j`, we query the Sparse Table to find the maximum `ey` in the range `[i+1, mid_j]` in `O(1)` time. Let this be `max_ey_middle`.
8.  If `max_ey_middle < rectangles[mid_j + 1].sy`, it means `mid_j` is a potential valid split, and there might be an even earlier one. So we search in the left half: `high = mid_j - 1`.
9.  If `max_ey_middle >= rectangles[mid_j + 1].sy`, `mid_j` is not a valid split, so we must search in the right half: `low = mid_j + 1`.
10. If the binary search finds any valid `j`, we can immediately return `true`.
11. If the main loop finishes, return `false`.

This entire process is encapsulated in the `check` function, which is called for both horizontal and vertical orientations.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    // Sparse Table for Range Maximum Query
    static class SparseTable {
        int[][] st;
        int[] logTable;
        int n;

        public SparseTable(int[] arr) {
            this.n = arr.length;
            this.logTable = new int[n + 1];
            logTable[1] = 0;
            for (int i = 2; i <= n; i++) {
                logTable[i] = logTable[i / 2] + 1;
            }

            int maxLog = logTable[n];
            this.st = new int[n][maxLog + 1];

            for (int i = 0; i < n; i++) {
                st[i][0] = arr[i];
            }

            for (int j = 1; j <= maxLog; j++) {
                for (int i = 0; i + (1 << j) <= n; i++) {
                    st[i][j] = Math.max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
                }
            }
        }

        public int query(int l, int r) {
            if (l > r) return Integer.MIN_VALUE;
            int j = logTable[r - l + 1];
            return Math.max(st[l][j], st[r - (1 << j) + 1][j]);
        }
    }

    public boolean canBeCut(int n, int[][] rectangles) {
        return check(rectangles, 1, 3) || check(rectangles, 0, 2);
    }

    private boolean check(int[][] rectangles, int startDim, int endDim) {
        int R = rectangles.length;
        if (R < 3) return false;

        int[][] rects = new int[R][4];
        for (int i = 0; i < R; i++) rects[i] = Arrays.copyOf(rectangles[i], 4);

        Arrays.sort(rects, Comparator.comparingInt(r -> r[startDim]));

        int[] endCoords = new int[R];
        for (int i = 0; i < R; i++) endCoords[i] = rects[i][endDim];
        SparseTable st = new SparseTable(endCoords);

        int[] prefixMaxEnd = new int[R];
        prefixMaxEnd[0] = rects[0][endDim];
        for (int i = 1; i < R; i++) {
            prefixMaxEnd[i] = Math.max(prefixMaxEnd[i - 1], rects[i][endDim]);
        }

        for (int i = 0; i < R - 2; i++) {
            if (prefixMaxEnd[i] < rects[i + 1][startDim]) {
                // First cut is valid. Search for a second cut in the suffix.
                int low = i + 1, high = R - 2, ans = -1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    int middleMaxEnd = st.query(i + 1, mid);
                    if (middleMaxEnd < rects[mid + 1][startDim]) {
                        ans = mid;
                        high = mid - 1; // Try to find an earlier split
                    } else {
                        low = mid + 1;
                    }
                }
                if (ans != -1) return true;
            }
        }
        return false;
    }
}
```
### Algorithm
This approach improves upon the quadratic solution by optimizing the search for the second cut. The overall structure of checking horizontal and vertical cuts separately and sorting the rectangles remains the same.

1.  Sort the rectangles by their starting coordinate (`sy` for horizontal).
2.  Iterate through all possible first split points `i` from `0` to `R-3`.
3.  For each `i`, check if a cut between `i` and `i+1` is valid: `max(ey for rects in {0..i}) < r_{i+1}.sy`. This check is `O(1)` after an initial `O(R)` precomputation of prefix maximums.
4.  If the first cut is valid, we then need to determine if the remaining suffix of rectangles, `{r_{i+1}, ..., r_{R-1}}`, can be partitioned by a second cut.
5.  To check if the suffix can be partitioned, we need to find if there exists a split point `j` (`i+1 <= j < R-1`) such that `max(ey for rects in {i+1..j}) < r_{j+1}.sy`.
6.  Instead of a linear scan for `j`, we can use binary search. For a fixed `i`, the function `f(j) = max(ey for rects in {i+1..j})` is monotonic (non-decreasing). The function `g(j) = r_{j+1}.sy` is also non-decreasing. We are looking for a `j` where `f(j) < g(j)`.
7.  To efficiently compute `f(j)` (a range maximum query) during the binary search, we can pre-build a data structure like a Sparse Table or a Segment Tree on the `ey` coordinates of all rectangles. A Sparse Table allows range maximum queries in `O(1)` time after an `O(R log R)` build time.
8.  For each `i`, we perform a binary search for `j` on the range `[i+1, R-2]`. If the binary search finds any valid `j`, we have found a solution.
9.  If the loop for `i` completes without finding a solution, no such horizontal cuts exist. The same logic is then applied for vertical cuts.

# Solutions
### Java

```java
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 ); } }
```

### JavaScript

```javascript
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 ); }
```

### CPP

```cpp
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 )); } };
```

### Python

```python
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 )
```