3197. Find the Minimum Area to Cover All Ones II

HardArrayEnumerationMatrix

Problem Description

You are given a 2D binary array grid. The task is to find 3 non-overlapping rectangles with non-zero areas that have horizontal and vertical sides, such that all the 1's in grid lie inside these rectangles. The goal is to return the minimum possible sum of the areas of these rectangles.

Note that these rectangles are allowed to touch each other.

Intuition

To solve this problem, the strategy involves dividing the grid into three non-overlapping rectangles such that each rectangle contains all the 1's it can encompass, and together they cover all 1's in the grid. The rectangles must be positioned in a way that minimizes the total area. The solution requires evaluating possible ways to split the grid:

Horizontal Splits: Try dividing the grid into three parts using two horizontal lines. This means we look at different pairs of rows for splitting.
Vertical Splits: Similarly, consider dividing the grid using two vertical lines.
Combined Splits: Evaluate combinations where a primary split (either horizontal or vertical) is followed by a secondary split within one of the resulting sections. This can be:
- A horizontal split followed by a vertical split in the top or bottom section.
- A vertical split followed by a horizontal split in the left or right section.

In each case, we need a function f(i1, j1, i2, j2) that calculates the minimum rectangle area which includes all 1's in the sub-grid from (i1, j1) to (i2, j2).

Through enumeration of these potential split strategies, and computing the areas of the rectangles for each scenario, we can determine the configuration that yields the smallest sum of areas, providing the desired solution.

Solution Approach

The solution approach revolves around an enumeration strategy to find the optimal splitting of the grid into three rectangles, each containing all possible 1s in the most space-efficient manner. The method involves investigating multiple configurations by dividing the grid and calculating the rectangular area covering all ones for each configuration. Here are the key steps and algorithmic considerations:

Enumeration Method

Two Horizontal Splits:
- Use two horizontal lines to divide the grid into three horizontal sections. Iterate over each possible pair of split rows and calculate the combined area of the rectangles encompassing all 1s in these sections.
Two Vertical Splits:
- Similarly, insert two vertical lines to split the grid into three vertical sections. Iterate over each possible pair of split columns to determine the minimal area of covering rectangles.
Mixed Split Configurations:
- Evaluate more complex configurations by combining horizontal and vertical splits:
  - Vertical then Horizontal: First split vertically, then split further horizontally within the left and right sections.
  - Horizontal then Vertical: First split horizontally, then split further vertically within the top and bottom sections.

Function Definition

Define a helper function f(i1, j1, i2, j2) that calculates the area of the smallest rectangle covering all 1s in the subgrid specified by the corners (i1, j1) to (i2, j2). This is achieved by determining the bounding box of all 1s in the specified region.

Iterative Calculation

Iterate through all possible configurations of row and column splits.
For each configuration, calculate the sum of areas of the three rectangles encompassing all 1s.
Keep track of the minimum sum encountered across all configurations.

Code Implementation

The core of this approach is realized in the implementation where nested loops explore each potential split pattern, utilizing the function f to compute the necessary rectangle area for each considered split.

By systematically evaluating these split configurations, the implementation derives the minimal sum of areas of three non-overlapping rectangles containing all the 1s, providing an optimal solution to the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider the following 2D binary array representing grid:

[
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
]

Our task is to find three non-overlapping rectangles that contain all the 1's, ensuring that the total area of these rectangles is minimized.

Step 1: Evaluate potential horizontal splits

We have the possibility to place two horizontal lines. Let's say we split between the first and second rows, and between the second and third rows:
- First rectangle: Top section (row 1 only) – Horizontal line between row 1 and row 2. Contains [0, 1, 0].
- Second rectangle: Middle section (row 2 only) – Contains [1, 0, 1].
- Third rectangle: Bottom section (row 3 only) – Contains [0, 1, 0].

For each section, calculate the enclosing rectangle:

Rectangle 1 contains all 1's at positions (0,1) within itself, so it's area is 1.
Rectangle 2 needs to cover (1,0) and (1,2) positions, so the area of this rectangle is 3.
Rectangle 3 includes the 1 at position (2,1), so the area is 1.

Total area for this configuration: 1 + 3 + 1 = 5.

Step 2: Evaluate potential vertical splits

Try placing two vertical lines: e.g., between the first and second column, and the second and third column.
- First rectangle: Left section (column 1) – Includes [0,1,0] from the leftmost column.
- Second rectangle: Middle section (column 2) – [1,0,1] from the middle column.
- Third rectangle: Right section (column 3) – [0,1,0] from the rightmost column.

Calculating enclosing rectangles:

Rectangle 1 involves 1 at (1,0) with an area of 3 for enclosing (0,0), (1,0), (2,0).
Rectangle 2 includes the 1's in positions (0,1), (2,1), with area 3.
Rectangle 3 entails the 1 at (1,2) with an area of 3.

Total area: 3 + 3 + 3 = 9.

Step 3: Evaluate mixed splits

Try a horizontal split followed by vertical within sections (and vice versa).
- Configuration 1: Horizontal between rows 1 and 2 followed by a vertical split in the bottom: (top), (bottom-left), (bottom-right) sections.
- Configuration 2: Vertical first then horizontal in sections: (left-top), (left-bottom), (right).

Each configuration's summed areas vary, and through repeating this process with combined and alternated primary/secondary splits, the minimal configuration is discovered.

Ultimately, through evaluating and comparing these configurations iteratively, choose the one with the smallest total area, which would be an optimal arrangement covering all 1's efficiently.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minimumSum(self, grid: List[List[int]]) -> int:
6        # Function to calculate the area of the rectangle covering all 1s in given subgrid
7        def f(i1: int, j1: int, i2: int, j2: int) -> int:
8            x1 = y1 = inf  # Initialize top-left corner as infinity
9            x2 = y2 = -inf # Initialize bottom-right corner as negative infinity
10            for i in range(i1, i2 + 1): # Traverse through rows in the subgrid
11                for j in range(j1, j2 + 1): # Traverse through columns in the subgrid
12                    if grid[i][j] == 1: # Check if the current cell contains 1
13                        x1 = min(x1, i) # Update the top-most row containing 1
14                        y1 = min(y1, j) # Update the left-most column containing 1
15                        x2 = max(x2, i) # Update the bottom-most row containing 1
16                        y2 = max(y2, j) # Update the right-most column containing 1
17            # Calculate the area of the rectangle covering all 1s
18            return (x2 - x1 + 1) * (y2 - y1 + 1)
19
20        m, n = len(grid), len(grid[0]) # Get dimensions of the grid
21        ans = m * n # Start with maximum possible area (entire grid)
22      
23        # Case 1: Split the grid horizontally into three parts
24        for i1 in range(m - 1):
25            for i2 in range(i1 + 1, m - 1):
26                ans = min(
27                    ans,
28                    f(0, 0, i1, n - 1)               # Area of first part
29                    + f(i1 + 1, 0, i2, n - 1)       # Area of second part
30                    + f(i2 + 1, 0, m - 1, n - 1)    # Area of third part
31                )
32      
33        # Case 2: Split the grid vertically into three parts
34        for j1 in range(n - 1):
35            for j2 in range(j1 + 1, n - 1):
36                ans = min(
37                    ans,
38                    f(0, 0, m - 1, j1)               # Area of first part
39                    + f(0, j1 + 1, m - 1, j2)       # Area of second part
40                    + f(0, j2 + 1, m - 1, n - 1)    # Area of third part
41                )
42      
43        # Case 3: Split the grid in other possible shapes
44        for i in range(m - 1):
45            for j in range(n - 1):
46                ans = min(
47                    ans,
48                    f(0, 0, i, j)                   # Area of first part
49                    + f(0, j + 1, i, n - 1)         # Area of second part
50                    + f(i + 1, 0, m - 1, n - 1)    # Area of third part
51                )
52                ans = min(
53                    ans,
54                    f(0, 0, i, n - 1)               # Area of first part
55                    + f(i + 1, 0, m - 1, j)        # Area of second part
56                    + f(i + 1, j + 1, m - 1, n - 1) # Area of third part
57                )
58                ans = min(
59                    ans,
60                    f(0, 0, i, j)                   # Area of first part
61                    + f(i + 1, 0, m - 1, j)        # Area of second part
62                    + f(0, j + 1, m - 1, n - 1)    # Area of third part
63                )
64                ans = min(
65                    ans,
66                    f(0, 0, m - 1, j)               # Area of first part
67                    + f(0, j + 1, i, n - 1)        # Area of second part
68                    + f(i + 1, j + 1, m - 1, n - 1) # Area of third part
69                )
70      
71        return ans
72

1class Solution {
2    // Constant to represent a large number, used for initialization.
3    private static final int INF = 1 << 30;
4    // The grid to perform operations on.
5    private int[][] grid;
6
7    // Method to find the minimum sum of areas required to cover given grid parts.
8    public int minimumSum(int[][] grid) {
9        // Store the grid in the class variable.
10        this.grid = grid;
11        int rows = grid.length;
12        int columns = grid[0].length;
13        // Variable to store the minimum sum of area results.
14        int minAreaSum = rows * columns;
15
16        // Iterate over all possible row partitions, choosing two split points.
17        for (int i1 = 0; i1 < rows - 1; i1++) {
18            for (int i2 = i1 + 1; i2 < rows - 1; i2++) {
19                // Update the minimum area sum by considering the current partition.
20                minAreaSum = Math.min(
21                    minAreaSum, 
22                    f(0, 0, i1, columns - 1) + f(i1 + 1, 0, i2, columns - 1) + f(i2 + 1, 0, rows - 1, columns - 1)
23                );
24            }
25        }
26
27        // Iterate over all possible column partitions, choosing two split points.
28        for (int j1 = 0; j1 < columns - 1; j1++) {
29            for (int j2 = j1 + 1; j2 < columns - 1; j2++) {
30                // Update the minimum area sum by considering the current partition.
31                minAreaSum = Math.min(
32                    minAreaSum, 
33                    f(0, 0, rows - 1, j1) + f(0, j1 + 1, rows - 1, j2) + f(0, j2 + 1, rows - 1, columns - 1)
34                );
35            }
36        }
37
38        // Iterate over mid-point partitions in the grid.
39        for (int i = 0; i < rows - 1; i++) {
40            for (int j = 0; j < columns - 1; j++) {
41                // Check different possible rectangular partitions and update the minimum area sum.
42                minAreaSum = Math.min(
43                    minAreaSum, 
44                    f(0, 0, i, j) + f(0, j + 1, i, columns - 1) + f(i + 1, 0, rows - 1, columns - 1)
45                );
46                minAreaSum = Math.min(
47                    minAreaSum, 
48                    f(0, 0, i, columns - 1) + f(i + 1, 0, rows - 1, j) + f(i + 1, j + 1, rows - 1, columns - 1)
49                );
50
51                minAreaSum = Math.min(
52                    minAreaSum, 
53                    f(0, 0, i, j) + f(i + 1, 0, rows - 1, j) + f(0, j + 1, rows - 1, columns - 1)
54                );
55                minAreaSum = Math.min(
56                    minAreaSum, 
57                    f(0, 0, rows - 1, j) + f(0, j + 1, i, columns - 1) + f(i + 1, j + 1, rows - 1, columns - 1)
58                );
59            }
60        }
61        return minAreaSum; // Return the minimum area sum found.
62    }
63
64    // Helper method to calculate the area of the subgrid defined by corners (i1, j1) and (i2, j2).
65    private int f(int i1, int j1, int i2, int j2) {
66        int minX = INF, minY = INF;
67        int maxX = -INF, maxY = -INF;
68        // Iterate over the specified subgrid and find the bounding rectangle for cells with value 1.
69        for (int i = i1; i <= i2; i++) {
70            for (int j = j1; j <= j2; j++) {
71                if (grid[i][j] == 1) {
72                    minX = Math.min(minX, i);
73                    minY = Math.min(minY, j);
74                    maxX = Math.max(maxX, i);
75                    maxY = Math.max(maxY, j);
76                }
77            }
78        }
79        // Return the area of the rectangle bounding all 1s within the specified subgrid.
80        return (maxX - minX + 1) * (maxY - minY + 1);
81    }
82}
83

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    int minimumSum(std::vector<std::vector<int>>& grid) {
8        int m = grid.size();                // Number of rows in the grid
9        int n = grid[0].size();             // Number of columns in the grid
10        int ans = m * n;                    // Initialize the minimum sum to the maximum possible value
11        int inf = INT_MAX / 4;              // Define a large number to handle integer operations and avoid overflow
12
13        // Lambda function to calculate the sum of a subgrid
14        auto f = [&](int i1, int j1, int i2, int j2) {
15            int x1 = inf, y1 = inf;         // Initialize the top-left corner of the subgrid
16            int x2 = -inf, y2 = -inf;       // Initialize the bottom-right corner of the subgrid
17
18            // Traverse the subgrid to find the bounding box of all '1's
19            for (int i = i1; i <= i2; i++) {
20                for (int j = j1; j <= j2; j++) {
21                    if (grid[i][j] == 1) {
22                        x1 = std::min(x1, i);  // Update the x-coordinate of the top-left corner
23                        y1 = std::min(y1, j);  // Update the y-coordinate of the top-left corner
24                        x2 = std::max(x2, i);  // Update the x-coordinate of the bottom-right corner
25                        y2 = std::max(y2, j);  // Update the y-coordinate of the bottom-right corner
26                    }
27                }
28            }
29
30            // If no '1' is found in the subgrid, return infinity to ignore this partition
31            return x1 > x2 || y1 > y2 ? inf : (x2 - x1 + 1) * (y2 - y1 + 1);
32        };
33
34        // Try partitioning the grid into 3 horizontal sections and calculate their sums
35        for (int i1 = 0; i1 < m - 1; i1++) {
36            for (int i2 = i1 + 1; i2 < m - 1; i2++) {
37                ans = std::min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) + f(i2 + 1, 0, m - 1, n - 1));
38            }
39        }
40
41        // Try partitioning the grid into 3 vertical sections and calculate their sums
42        for (int j1 = 0; j1 < n - 1; j1++) {
43            for (int j2 = j1 + 1; j2 < n - 1; j2++) {
44                ans = std::min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) + f(0, j2 + 1, m - 1, n - 1));
45            }
46        }
47
48        // Try different combinations of horizontal and vertical cuts
49        for (int i = 0; i < m - 1; i++) {
50            for (int j = 0; j < n - 1; j++) {
51                ans = std::min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) + f(i + 1, 0, m - 1, n - 1));
52                ans = std::min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) + f(i + 1, j + 1, m - 1, n - 1));
53                ans = std::min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) + f(0, j + 1, m - 1, n - 1));
54                ans = std::min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) + f(i + 1, j + 1, m - 1, n - 1));
55            }
56        }
57
58        return ans;  // Return the minimum sum of the partitions
59    }
60};
61

1/**
2 * Finds the minimum sum of three non-overlapping submatrices in the given grid.
3 * Assumes the grid is filled with 0s and 1s.
4 *
5 * @param grid - A 2D number array representing the grid.
6 * @returns The minimum sum of the areas of the three submatrices.
7 */
8function minimumSum(grid: number[][]): number {
9    const m = grid.length;
10    const n = grid[0].length;
11    let ans = m * n; // Initialize `ans` with the largest possible area (the whole grid)
12    const inf = Number.MAX_SAFE_INTEGER; // A large number to represent infinity
13
14    // Function to calculate the area of the submatrix from (i1, j1) to (i2, j2)
15    const f = (i1: number, j1: number, i2: number, j2: number): number => {
16        let [minRow, minCol] = [inf, inf];
17        let [maxRow, maxCol] = [-inf, -inf];
18      
19        // Traverse the submatrix to find the bounding rectangle of 1s
20        for (let i = i1; i <= i2; i++) {
21            for (let j = j1; j <= j2; j++) {
22                if (grid[i][j] === 1) {
23                    minRow = Math.min(minRow, i);
24                    minCol = Math.min(minCol, j);
25                    maxRow = Math.max(maxRow, i);
26                    maxCol = Math.max(maxCol, j);
27                }
28            }
29        }
30
31        // If no '1' is found, the area is 0, otherwise calculate the area of the rectangle
32        return minRow === inf ? 0 : (maxRow - minRow + 1) * (maxCol - minCol + 1);
33    };
34
35    // Iterate using two horizontal cuts and calculate the minimal sum
36    for (let i1 = 0; i1 < m - 1; i1++) {
37        for (let i2 = i1 + 1; i2 < m - 1; i2++) {
38            ans = Math.min(
39                ans,
40                f(0, 0, i1, n - 1) + // First submatrix
41                f(i1 + 1, 0, i2, n - 1) + // Second submatrix
42                f(i2 + 1, 0, m - 1, n - 1) // Third submatrix
43            );
44        }
45    }
46
47    // Iterate using two vertical cuts and calculate the minimal sum
48    for (let j1 = 0; j1 < n - 1; j1++) {
49        for (let j2 = j1 + 1; j2 < n - 1; j2++) {
50            ans = Math.min(
51                ans,
52                f(0, 0, m - 1, j1) + // First submatrix
53                f(0, j1 + 1, m - 1, j2) + // Second submatrix
54                f(0, j2 + 1, m - 1, n - 1) // Third submatrix
55            );
56        }
57    }
58
59    // Iterate using a combination of horizontal and vertical cuts
60    for (let i = 0; i < m - 1; i++) {
61        for (let j = 0; j < n - 1; j++) {
62            // Various ways to cut the grid into three parts
63            ans = Math.min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) + f(i + 1, 0, m - 1, n - 1));
64            ans = Math.min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) + f(i + 1, j + 1, m - 1, n - 1));
65            ans = Math.min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) + f(0, j + 1, m - 1, n - 1));
66            ans = Math.min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) + f(i + 1, j + 1, m - 1, n - 1));
67        }
68    }
69
70    return ans;
71}
72

Time and Space Complexity

The function f iterates over a rectangular subgrid defined by two pairs of indices. In the worst case, it iterates over the entire grid, running in O(m * n) time, where m and n are the dimensions of the grid.

The outer loops that define subgrid boundaries run in O(m^2 * n^2) time in total:

The first set of loops operates on rows and runs in O(m^2) because it selects pairs of rows (i1 and i2) and in each iteration calculates three f functions.
The second set of loops operates on columns and also runs in O(n^2) by selecting pairs of columns (j1 and j2).
The third set of loops accounts for slicing the grid into subgrids defined by individual entry points within the grid and potentially involves up to O(m * n) iterations due to iteration on every element.

Thus, each call to f is over a subgrid of the grid and collectively, the calls accumulate to an O(m^2 * n^2) time complexity.

The space complexity is O(1) because no additional space is utilized that scales with the input size. The function f and loops operate directly on the input grid without creating substantial auxiliary data structures.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know