3394. Check-If-Grid-Can-Be-Cut-Into-Sections

Having this question after yesterdays seems criminal but anyways.

Reading this question after yesterday’s one, we realize that this is a very similar question. We can try to find the “gaps” between the rectangles in the same way we did yesterday.

The only thing that we need to change is that we need to check for both the x direction and the y direction as we can cut the grid in both directions.

We can do this with some preprocessing to separate the rectangles array into two arrays, one for the x direction and one for the y direction. Then we can use the same algorithm that we used yesterday to find the gaps in the x direction and the y direction.

We return True when we find that the number of gaps is 2 (as soon as there are two gaps between the rectangles, we can cut the grid there).

class Solution(object):
    def checkValidCuts(self, n, rectangles):
        """
        :type n: int
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        xList = []
        yList = []

        for startx, starty, endx, endy in rectangles:
            xList.append((startx, endx))
            yList.append((starty, endy))

        xList.sort()
        yList.sort()

        latestx = xList[0][1]
        latesty = yList[0][1]

        countx = 0
        county = 0

        for i in range(1, len(xList)):
            startx, endx = xList[i]
            starty, endy = yList[i]

            if startx >= latestx:
                countx += 1
            if starty >= latesty:
                county += 1
            
            latestx = max(latestx, endx)
            latesty = max(latesty, endy)

            if countx == 2 or county == 2:
                return True
                
        return False

Time Complexity: O(n log n)

Space Complexity: O(n)