Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3657. Check if Grid can be Cut into Sections

My accepted Python solution to LeetCode problem 3657, Check if Grid can be Cut into Sections, running in 515ms.

  • Difficulty: Medium
  • Python
  • Runtime 515ms
  • Memory 76.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 515ms, memory 76.4MB, accepted 2025-12-31.

python
class Solution:
    def checkValidCuts(self, n: int, rectangles: List[List[int]]) -> bool:
        def canCut(intervals):
            # Sort by start position
            intervals.sort()
            
            # Merge overlapping intervals and count gaps
            merged_end = intervals[0][1]
            gaps = 0
            
            for start, end in intervals[1:]:
                if start >= merged_end:
                    gaps += 1
                    if gaps >= 2:
                        return True
                merged_end = max(merged_end, end)
            
            return gaps >= 2
        
        # Extract horizontal intervals (y-coordinates)
        horizontal = [[r[1], r[3]] for r in rectangles]
        
        # Extract vertical intervals (x-coordinates)
        vertical = [[r[0], r[2]] for r in rectangles]
        
        return canCut(horizontal) or canCut(vertical)

Source