Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3459. Find the Minimum Area to Cover All Ones II

My accepted Python solution to LeetCode problem 3459, Find the Minimum Area to Cover All Ones II, running in 6583ms.

  • Difficulty: Hard
  • Python
  • Runtime 6583ms
  • Memory 17.5MB

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 6583ms, memory 17.5MB, accepted 2025-12-30.

python
class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def min_area(r1, r2, c1, c2):
            """Calculate minimum rectangle area to cover all 1s in subgrid"""
            min_r, max_r = m, -1
            min_c, max_c = n, -1
            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if grid[r][c] == 1:
                        min_r = min(min_r, r)
                        max_r = max(max_r, r)
                        min_c = min(min_c, c)
                        max_c = max(max_c, c)
            if max_r == -1:  # No 1s in this region
                return 0
            return (max_r - min_r + 1) * (max_c - min_c + 1)
        
        ans = float('inf')
        
        # Try all ways to split grid into 3 non-overlapping rectangles
        # Case 1: 3 horizontal strips
        for i in range(m - 2):
            for j in range(i + 1, m - 1):
                area = min_area(0, i, 0, n-1) + min_area(i+1, j, 0, n-1) + min_area(j+1, m-1, 0, n-1)
                ans = min(ans, area)
        
        # Case 2: 3 vertical strips
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                area = min_area(0, m-1, 0, i) + min_area(0, m-1, i+1, j) + min_area(0, m-1, j+1, n-1)
                ans = min(ans, area)
        
        # Case 3: 1 horizontal strip + 2 vertical (top strip + 2 below)
        for i in range(m - 1):
            for j in range(n - 1):
                # Top strip, bottom-left, bottom-right
                area = min_area(0, i, 0, n-1) + min_area(i+1, m-1, 0, j) + min_area(i+1, m-1, j+1, n-1)
                ans = min(ans, area)
        
        # Case 4: 2 vertical (top) + 1 horizontal strip (bottom)
        for i in range(m - 1):
            for j in range(n - 1):
                # Top-left, top-right, bottom strip
                area = min_area(0, i, 0, j) + min_area(0, i, j+1, n-1) + min_area(i+1, m-1, 0, n-1)
                ans = min(ans, area)
        
        # Case 5: 1 vertical strip + 2 horizontal (left strip + 2 right)
        for j in range(n - 1):
            for i in range(m - 1):
                # Left strip, top-right, bottom-right
                area = min_area(0, m-1, 0, j) + min_area(0, i, j+1, n-1) + min_area(i+1, m-1, j+1, n-1)
                ans = min(ans, area)
        
        # Case 6: 2 horizontal (left) + 1 vertical strip (right)
        for j in range(n - 1):
            for i in range(m - 1):
                # Top-left, bottom-left, right strip
                area = min_area(0, i, 0, j) + min_area(i+1, m-1, 0, j) + min_area(0, m-1, j+1, n-1)
                ans = min(ans, area)
        
        return ans

Source