3394.Check_if_Grid_can_be_Cut_into_Sections(Medium).md

3394. Check if Grid can be Cut into Sections (Medium)

Date and Time: Apr 1, 2025

Link: https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections

Walk-through:

First we can extract x, y coordinates as intervals from rectangles. Then, we sort x_intervals, y_intervals base on the start_x, start_y.

Next, we use variable maxEnd to compare with each start to increment cnts, also update maxEnd = max(maxEnd, end) each time. By maintaining maxEnd, we make sure every start <= maxEnd will be check, and if any of these rectangles have end > maxEnd will update the current maxEnd, results in no cut for these rectangles.

Finally we check if either x_intervals or y_intervals can have more than 2 cuts.

Python Solution:

class Solution:
    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
        # Sort x-coordinate and y-coordinate, use max_end to keep track of the current max_end x and max_end y, if start_x >= max_endX, there is a gap
        # If gaps >= 2, we can separate

        # TC: O(nlogn), SC: O(n)
        def check(intervals):
            intervals.sort()
            cnts = 0
            maxEnd = intervals[0][1]
            for start, end in intervals:
                if start >= maxEnd:
                    cnts += 1
                # Always update maxEnd to the greater end
                maxEnd = max(maxEnd, end)
            return cnts >= 2

        x_intervals = [[rec[0], rec[2]] for rec in rectangles]
        y_intervals = [[rec[1], rec[3]] for rec in rectangles]
        return check(x_intervals) or check(y_intervals)

Time Complexity: $O(nlog(n))$
Space Complexity: $O(n)$