Today’s Problem

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

Intuition

This question asks about merging sections. In this case, if we smash it into 1D array, it just means “Is there more than two gaps inside the section?”

Approach

Therefore, we can sort the list, and then iterate the whole list and see whether there is a gap between the section we already iterated and the new section. If there is, then add 1, else, merge this new section to our old section. The thing is that you need to do it twice.

Complexity

  • Time complexity: $O(N)$, N is the length of rectangles.
  • Space complexity: $O(1)$.

Code


class Solution:

    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:

        N = len(rectangles)

        def get_res(a,b):

            rectangles.sort(key = lambda x: (x[a], x[b]))

            gapCnt,maxPos,l = 0,1,0

            while(l < N):

                while(l < N and rectangles[l][a] < maxPos):

                    maxPos = max(maxPos, rectangles[l][b])

                    l += 1

                if l == N:

                    break

                else:

                    gapCnt += 1

                    maxPos = rectangles[l][b]


                # print(a,l)


            if gapCnt > 1:

                return True

            return False


        return get_res(0,2) or get_res(1,3)