LeetCode Solutions Blog

Check if Grid can be Cut into Sections

Number: 3657

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an n x n grid and a list of non‐overlapping rectangles (each defined by its bottom‐left and top‐right coordinates), determine whether it is possible to make either two horizontal cuts or two vertical cuts (i.e. full-length lines across the grid) so that the grid is partitioned into three sections where: • Each section contains at least one rectangle. • Each rectangle lies completely in exactly one section (i.e. no cut goes through any rectangle).

Key Insights

Since a cut is a full line, it may only be placed on coordinates that are exactly a rectangle’s boundary (start or end) to avoid “cutting” a rectangle.
A valid horizontal (or vertical) cut at coordinate c is safe if for every rectangle either the rectangle’s top is ≤ c or its bottom is ≥ c.
Because the cut must separate the rectangles completely, one must partition the rectangles into three nonempty groups such that all rectangles in the lower group lie entirely below the first cut, all rectangles in the middle group lie completely between the two cuts, and all rectangles in the upper group lie completely above the second cut.
The counts of rectangles that lie “entirely below” a candidate cut (using top boundaries) and “entirely above” a candidate cut (using bottom boundaries) are monotonic when the candidate cut is taken from the sorted unique boundaries.
The problem has a symmetric “horizontal” and “vertical” version. If either possibility yields a valid pair of cuts – two horizontal or two vertical – then the answer is true.

Space and Time Complexity

Time Complexity: O(m log m) per orientation, where m is the number of unique boundaries (at most 2 · (rectangles.length)). Overall O(m log m) since the two orientations are handled similarly. Space Complexity: O(m) for storing the candidate cut positions and auxiliary arrays.

Solution

The solution considers both horizontal and vertical cutting possibilities. For a fixed orientation (say horizontal), we first extract the y‐coordinates that are “candidate” cut lines (all rectangle start_y and end_y values). Using two sorted arrays – one for rectangle top boundaries (end_y) and one for bottom boundaries (start_y) – we can for any candidate coordinate c quickly determine: • group1_count: number of rectangles completely below or touching c (i.e. with top ≤ c) • group3_count: number of rectangles completely above or touching c (i.e. with bottom ≥ c) A valid pair of candidate cuts (L, R with L < R) satisfies: – group1_count(L) ≥ 1 (at least one rectangle is completely below L), – group3_count(R) ≥ 1 (at least one rectangle is completely above R), and – The “middle” group count (which is total – group1_count(L) – group3_count(R)) is at least 1. Because the counts are monotonic over the candidate boundaries, we can iterate over possible L and use a binary search (or two‑pointer technique) to find a corresponding valid R. We then repeat the same process for vertical cuts (using x boundaries). If either horizontal or vertical partitioning works, we return true.

Code Solutions

import bisect

def can_cut(rectangles, total, starts, tops, candidates):
    # candidates: sorted unique coordinates (could be x or y boundaries)
    # starts: sorted list of rectangle starting coordinates (for group3: count of rect with coordinate >= candidate)
    # tops: sorted list of rectangle ending coordinates (for group1: count of rect with coordinate <= candidate)
    n = total
    m = len(candidates)
    # For a candidate cut c:
    # group1_count = number of rectangles with top <= c  => use bisect_right on tops
    # group3_count = number of rectangles with start >= c => = n - bisect_left(starts, c)
    # We want to find indices i < j in candidates such that:
    #   group1_count(candidates[i]) >= 1,
    #   group3_count(candidates[j]) >= 1, and
    #   n - group1_count(candidates[i]) - group3_count(candidates[j]) >= 1.
    
    # For each candidate L, attempt to find some candidate R > L that satisfies conditions.
    for i in range(m - 1):
        L = candidates[i]
        group1 = bisect.bisect_right(tops, L)
        # Must have at least one rectangle completely below or on L.
        if group1 < 1 or group1 == n:
            continue
        # We require: middle group count = n - group1 - group3 > 0,
        # that is, group3 < n - group1.
        # Now, since candidates are sorted, and the count group3 = n - bisect_left(starts, candidate)
        # is non-increasing as candidate increases (because bisect_left returns a higher index),
        # we can binary search for the first candidate in candidates[i+1:] such that
        # group3_count < n - group1.
        lo, hi = i + 1, m - 1
        valid_R_found = False
        while lo <= hi:
            mid = (lo + hi) // 2
            R = candidates[mid]
            group3 = n - bisect.bisect_left(starts, R)
            if group3 < n - group1:
                valid_R_found = True
                hi = mid - 1
            else:
                lo = mid + 1
        # If a valid R candidate is found, check that group3 count is at least 1.
        if valid_R_found:
            # Verify candidate R (using the smallest found) satisfies group3_count >= 1.
            R = candidates[lo] if lo < m else candidates[m-1]
            group3 = n - bisect.bisect_left(starts, R)
            if group3 >= 1 and (n - group1 - group3) >= 1:
                return True
    return False

def checkCuts(n, rectangles):
    total = len(rectangles)
    # Horizontal possibility (cuts along y direction)
    # Extract y boundaries: bottom -> start_y, top -> end_y
    y_starts = []
    y_tops = []
    y_candidates_set = set()
    for rect in rectangles:
        start_y = rect[1]
        end_y = rect[3]
        y_starts.append(start_y)
        y_tops.append(end_y)
        y_candidates_set.add(start_y)
        y_candidates_set.add(end_y)
    y_starts.sort()
    y_tops.sort()
    y_candidates = sorted(list(y_candidates_set))
    
    horizontal_possible = can_cut(rectangles, total, y_starts, y_tops, y_candidates)
    
    # Vertical possibility (cuts along x direction)
    x_starts = []
    x_ends = []
    x_candidates_set = set()
    for rect in rectangles:
        start_x = rect[0]
        end_x = rect[2]
        x_starts.append(start_x)
        x_ends.append(end_x)
        x_candidates_set.add(start_x)
        x_candidates_set.add(end_x)
    x_starts.sort()
    x_ends.sort()
    x_candidates = sorted(list(x_candidates_set))
    
    vertical_possible = can_cut(rectangles, total, x_starts, x_ends, x_candidates)
    
    return horizontal_possible or vertical_possible

# Example usage:
if __name__ == "__main__":
    # Example 1:
    n = 5
    rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
    print(checkCuts(n, rectangles))  # Expected output: True