LeetCode 3197 - Find the Minimum Area to Cover All Ones II

The problem gives us a binary matrix grid, where each cell contains either 0 or 1. Our goal is to place exactly three non-overlapping axis-aligned rectangles so that every cell containing 1 is covered by at least one rectangle.

leetcodehardarraymatrixenumeration

LeetCode Problem 3197

Difficulty: 🔴 Hard
Topics: Array, Matrix, Enumeration

Solution

Problem Understanding

The problem gives us a binary matrix grid, where each cell contains either 0 or 1. Our goal is to place exactly three non-overlapping axis-aligned rectangles so that every cell containing 1 is covered by at least one rectangle.

Each rectangle must satisfy several conditions:

  • Its sides must be parallel to the grid axes.
  • It must have non-zero area.
  • The three rectangles cannot overlap, although touching edges is allowed.
  • Every 1 in the matrix must lie inside at least one of the rectangles.

The objective is to minimize the sum of the areas of the three rectangles.

A rectangle is defined by its top row, bottom row, left column, and right column. The area is:

$$(bottom - top + 1) \times (right - left + 1)$$

Importantly, rectangles may contain 0s inside them. We are not required to tightly wrap individual 1s unless doing so minimizes the total area.

The grid dimensions are at most 30 x 30, which is relatively small. However, brute forcing all possible rectangles and all ways to assign cells to rectangles would still explode combinatorially. The small constraints suggest that an optimized enumeration approach is expected.

A key observation is that any optimal arrangement of three non-overlapping rectangles partitions the grid into three disjoint regions using horizontal and vertical cuts. Since rectangles are axis-aligned and non-overlapping, the layout must fall into one of a small number of geometric partition patterns.

Several edge cases are important:

  • The 1s may already form three isolated cells, in which case the answer is 3.
  • Many 1s may cluster together, forcing one large rectangle.
  • A rectangle may legally contain large empty regions if that reduces the total number of rectangles needed.
  • Rectangles may touch edges or corners, but they cannot overlap.
  • The grid may contain only a few rows or columns, so careful boundary handling is required.

Approaches

Brute Force Approach

A naive solution would enumerate every possible rectangle in the grid and then try every combination of three rectangles.

For each triple of rectangles, we would verify:

  1. The rectangles do not overlap.
  2. Every 1 in the grid is covered.
  3. Compute the total area.

A 30 x 30 grid contains roughly:

$$O(m^2 n^2)$$

possible rectangles, because we choose top, bottom, left, and right boundaries.

That means the total number of rectangle triples becomes:

$$O((m^2 n^2)^3)$$

which is astronomically large and completely infeasible.

Even aggressive pruning would not make this practical.

Key Insight

The crucial observation is that three non-overlapping rectangles partition the grid in only a limited number of structural ways.

Instead of enumerating arbitrary rectangles, we enumerate partitions of the grid into three regions. For each region, we compute the minimum bounding rectangle containing all 1s inside that region.

Since the rectangles are independent after partitioning, the optimal rectangle for a region is simply the tight bounding box around its 1s.

There are only six meaningful partition patterns:

  1. Three horizontal strips
  2. Three vertical strips
  3. Top strip + bottom split vertically
  4. Bottom strip + top split vertically
  5. Left strip + right split horizontally
  6. Right strip + left split horizontally

For every partition, we compute:

  • The minimal bounding rectangle area for each region
  • The sum of the three areas
  • The minimum over all partitions

Because the grid is small, exhaustive enumeration of partition lines is efficient.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((m²n²)³) O(1) Enumerates all rectangle triples
Optimal O(m²n²(m+n)) O(m²n²) Enumerates only valid partition structures

Algorithm Walkthrough

Step 1: Precompute Bounding Rectangle Areas

We define a helper function:

$$area(r1, c1, r2, c2)$$

This function returns the area of the smallest rectangle covering all 1s inside the subgrid.

To compute it:

  • Scan the subgrid

  • Track:

  • minimum row containing 1

  • maximum row containing 1

  • minimum column containing 1

  • maximum column containing 1

If the region contains no 1s, return 0.

Otherwise:

$$(maxRow - minRow + 1) \times (maxCol - minCol + 1)$$

Because many regions are queried repeatedly, we memoize results.

Step 2: Enumerate Three Horizontal Strips

We choose two horizontal cuts:

  • First cut after row i
  • Second cut after row j

This creates:

  1. Rows [0..i]
  2. Rows [i+1..j]
  3. Rows [j+1..m-1]

Each spans all columns.

We compute the minimal bounding rectangle area inside each strip and sum them.

Step 3: Enumerate Three Vertical Strips

Similarly, choose two vertical cuts:

  • First cut after column i
  • Second cut after column j

This creates three vertical regions.

Again compute the sum of minimal bounding areas.

Step 4: Enumerate Mixed Partitions

Now consider layouts where one region occupies the full width or height, and the remaining space is split.

Example:

  • Top strip
  • Bottom-left region
  • Bottom-right region

We enumerate:

  • The separating horizontal cut
  • The vertical split in the lower portion

We repeat this for all four asymmetric orientations.

Step 5: Track the Minimum

For every valid partition:

  • Compute three region areas
  • Sum them
  • Update the global minimum

Why it works

Every set of three non-overlapping axis-aligned rectangles induces a planar partition of the grid. Any such arrangement can always be represented by one of the six partition structures enumerated above.

Within a fixed region, the minimum-area rectangle covering all 1s is uniquely the bounding box of those 1s. Therefore, evaluating all partition structures guarantees that we examine the optimal arrangement.

Since we take the minimum over all possible partitions, the algorithm always returns the globally optimal answer.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        @lru_cache(None)
        def area(r1: int, c1: int, r2: int, c2: int) -> int:
            min_row = rows
            max_row = -1
            min_col = cols
            max_col = -1

            for r in range(r1, r2 + 1):
                for c in range(c1, c2 + 1):
                    if grid[r][c] == 1:
                        min_row = min(min_row, r)
                        max_row = max(max_row, r)
                        min_col = min(min_col, c)
                        max_col = max(max_col, c)

            if max_row == -1:
                return 0

            return (max_row - min_row + 1) * (max_col - min_col + 1)

        answer = float('inf')

        # Three horizontal strips
        for r1 in range(rows - 2):
            for r2 in range(r1 + 1, rows - 1):
                total = (
                    area(0, 0, r1, cols - 1) +
                    area(r1 + 1, 0, r2, cols - 1) +
                    area(r2 + 1, 0, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        # Three vertical strips
        for c1 in range(cols - 2):
            for c2 in range(c1 + 1, cols - 1):
                total = (
                    area(0, 0, rows - 1, c1) +
                    area(0, c1 + 1, rows - 1, c2) +
                    area(0, c2 + 1, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        # Top strip + bottom split vertically
        for r in range(rows - 1):
            for c in range(cols - 1):
                total = (
                    area(0, 0, r, cols - 1) +
                    area(r + 1, 0, rows - 1, c) +
                    area(r + 1, c + 1, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        # Bottom strip + top split vertically
        for r in range(rows - 1):
            for c in range(cols - 1):
                total = (
                    area(0, 0, r, c) +
                    area(0, c + 1, r, cols - 1) +
                    area(r + 1, 0, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        # Left strip + right split horizontally
        for c in range(cols - 1):
            for r in range(rows - 1):
                total = (
                    area(0, 0, rows - 1, c) +
                    area(0, c + 1, r, cols - 1) +
                    area(r + 1, c + 1, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        # Right strip + left split horizontally
        for c in range(cols - 1):
            for r in range(rows - 1):
                total = (
                    area(0, 0, r, c) +
                    area(r + 1, 0, rows - 1, c) +
                    area(0, c + 1, rows - 1, cols - 1)
                )
                answer = min(answer, total)

        return answer

The implementation begins by defining the memoized area() helper. This function computes the smallest bounding rectangle covering all 1s within a subgrid.

Memoization is essential because the same regions are queried repeatedly across different partition configurations.

The algorithm then systematically enumerates all six partition types. For each partition:

  1. The grid is divided into three disjoint regions.
  2. The minimum covering rectangle area for each region is computed.
  3. Their sum is compared against the current best answer.

The final answer is the minimum total area across all valid partitions.

Go Solution

package main

import "math"

func minimumSum(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	type Key struct {
		r1, c1, r2, c2 int
	}

	cache := make(map[Key]int)

	area := func(r1, c1, r2, c2 int) int {
		key := Key{r1, c1, r2, c2}

		if val, exists := cache[key]; exists {
			return val
		}

		minRow := rows
		maxRow := -1
		minCol := cols
		maxCol := -1

		for r := r1; r <= r2; r++ {
			for c := c1; c <= c2; c++ {
				if grid[r][c] == 1 {
					if r < minRow {
						minRow = r
					}
					if r > maxRow {
						maxRow = r
					}
					if c < minCol {
						minCol = c
					}
					if c > maxCol {
						maxCol = c
					}
				}
			}
		}

		if maxRow == -1 {
			cache[key] = 0
			return 0
		}

		result := (maxRow - minRow + 1) * (maxCol - minCol + 1)
		cache[key] = result
		return result
	}

	answer := math.MaxInt32

	// Three horizontal strips
	for r1 := 0; r1 < rows-2; r1++ {
		for r2 := r1 + 1; r2 < rows-1; r2++ {
			total :=
				area(0, 0, r1, cols-1) +
					area(r1+1, 0, r2, cols-1) +
					area(r2+1, 0, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	// Three vertical strips
	for c1 := 0; c1 < cols-2; c1++ {
		for c2 := c1 + 1; c2 < cols-1; c2++ {
			total :=
				area(0, 0, rows-1, c1) +
					area(0, c1+1, rows-1, c2) +
					area(0, c2+1, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	// Top strip + bottom split vertically
	for r := 0; r < rows-1; r++ {
		for c := 0; c < cols-1; c++ {
			total :=
				area(0, 0, r, cols-1) +
					area(r+1, 0, rows-1, c) +
					area(r+1, c+1, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	// Bottom strip + top split vertically
	for r := 0; r < rows-1; r++ {
		for c := 0; c < cols-1; c++ {
			total :=
				area(0, 0, r, c) +
					area(0, c+1, r, cols-1) +
					area(r+1, 0, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	// Left strip + right split horizontally
	for c := 0; c < cols-1; c++ {
		for r := 0; r < rows-1; r++ {
			total :=
				area(0, 0, rows-1, c) +
					area(0, c+1, r, cols-1) +
					area(r+1, c+1, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	// Right strip + left split horizontally
	for c := 0; c < cols-1; c++ {
		for r := 0; r < rows-1; r++ {
			total :=
				area(0, 0, r, c) +
					area(r+1, 0, rows-1, c) +
					area(0, c+1, rows-1, cols-1)

			if total < answer {
				answer = total
			}
		}
	}

	return answer
}

The Go implementation mirrors the Python logic closely. Since Go does not support decorators like lru_cache, we manually memoize rectangle areas using a map.

The Key struct uniquely identifies a subgrid by storing its boundaries.

Go integers are sufficient because the maximum possible area is only:

$$30 \times 30 = 900$$

so overflow is not a concern.

Worked Examples

Example 1

Input:

grid = [
  [1,0,1],
  [1,1,1]
]

The algorithm considers all partition structures.

One optimal partition is:

Region Covered Cells Bounding Rectangle Area
Left (0,0), (1,0) rows 0-1, cols 0-0 2
Middle (1,1) rows 1-1, cols 1-1 1
Right (0,2), (1,2) rows 0-1, cols 2-2 2

Total:

$$2 + 1 + 2 = 5$$

No other partition produces a smaller total.

Final answer:

5

Example 2

Input:

grid = [
  [1,0,1,0],
  [0,1,0,1]
]

One optimal configuration:

Region Covered Cells Bounding Rectangle Area
Top-left pair (0,0), (0,2) rows 0-0, cols 0-2 3
Middle (1,1) single cell 1
Right (1,3) single cell 1

Total:

$$3 + 1 + 1 = 5$$

Final answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(m²n²(m+n)) Enumerating all partition cuts and computing cached subgrid areas
Space O(m²n²) Memoization of subgrid area computations

The grid dimensions are at most 30 x 30, so this complexity is comfortably fast enough.

The expensive operation is computing bounding boxes for subgrids, but memoization ensures each subgrid is processed only once.

Test Cases

from typing import List

s = Solution()

# Provided example 1
assert s.minimumSum([[1,0,1],[1,1,1]]) == 5

# Provided example 2
assert s.minimumSum([[1,0,1,0],[0,1,0,1]]) == 5

# Three isolated ones
assert s.minimumSum([
    [1,0,0],
    [0,1,0],
    [0,0,1]
]) == 3

# All ones in a single row
assert s.minimumSum([
    [1,1,1]
]) == 3

# All ones in a single column
assert s.minimumSum([
    [1],
    [1],
    [1]
]) == 3

# Dense block
assert s.minimumSum([
    [1,1],
    [1,1]
]) == 4

# Sparse corners
assert s.minimumSum([
    [1,0,0,1],
    [0,0,0,0],
    [1,0,0,1]
]) == 6

# Large empty gaps
assert s.minimumSum([
    [1,0,0,0,1],
    [0,0,0,0,0],
    [0,1,0,0,0]
]) == 5

# Multiple clustered groups
assert s.minimumSum([
    [1,1,0,0],
    [1,1,0,1],
    [0,0,0,1]
]) == 6

Test Summary

Test Why
Example 1 Validates mixed partition handling
Example 2 Validates disconnected points
Three isolated ones Ensures minimal area can be exactly 3
Single row Tests horizontal edge case
Single column Tests vertical edge case
Dense block Ensures rectangles may overlap logically via partitioning
Sparse corners Tests distant groups
Large empty gaps Verifies rectangles may include zeros
Multiple clustered groups Tests irregular clustering

Edge Cases

One important edge case occurs when all 1s are isolated from each other. In this situation, the optimal strategy is often to assign one rectangle per cell, producing a total area equal to the number of covered cells. A careless implementation might accidentally merge distant cells into unnecessarily large rectangles. Our solution avoids this because every partition computes the tight bounding box independently.

Another tricky case occurs when the grid has only one row or one column. Many partitioning algorithms accidentally assume at least two dimensions exist. Our implementation carefully uses loop bounds such as rows - 1 and cols - 1, ensuring partitions remain valid even in degenerate grids.

A third subtle case is when a region contains no 1s at all. If this is not handled carefully, the bounding rectangle computation may produce invalid coordinates or negative areas. Our area() helper explicitly returns 0 when no 1 exists inside a region, which safely handles empty partitions.

A final edge case involves rectangles touching at borders. The problem allows touching but forbids overlapping. Since our partitions divide the grid into disjoint regions using exact cut lines, rectangles may share edges naturally without ever overlapping, which exactly matches the problem requirements.