Find the Minimum Area to Cover All Ones II

Hard

#2840Time: O(m^2 * n^2). The dominant part is handling the T-shaped cuts. There are O(m*n) possible cut intersections. For each, we call `getArea` three times. Each `getArea` call can take up to O(m*n) time in the worst case. This leads to a total complexity of O(m*n * m*n) = O(m^2 * n^2). The parallel cut cases have complexities of O(m*n^3) and O(n*m^3), which are lower for square-like grids.Space: O(1) besides the input grid storage.

Patterns

Enumeration

Data structures

Array Matrix

Prompt

You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles.

Return the minimum possible sum of the area of these rectangles.

Note that the rectangles are allowed to touch.

Example 1:

Input: grid = [[1,0,1],[1,1,1]]

Output: 5

Explanation:

The 1's at (0, 0) and (1, 0) are covered by a rectangle of area 2.
The 1's at (0, 2) and (1, 2) are covered by a rectangle of area 2.
The 1 at (1, 1) is covered by a rectangle of area 1.

Example 2:

Input: grid = [[1,0,1,0],[0,1,0,1]]

Output: 5

Explanation:

The 1's at (0, 0) and (0, 2) are covered by a rectangle of area 3.
The 1 at (1, 1) is covered by a rectangle of area 1.
The 1 at (1, 3) is covered by a rectangle of area 1.

Constraints:

1 <= grid.length, grid[i].length <= 30
grid[i][j] is either 0 or 1.
The input is generated such that there are at least three 1's in grid.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible way to partition the grid into three non-overlapping rectangles. There are six fundamental patterns for such a partition: two parallel vertical cuts, two parallel horizontal cuts, and four 'T'-shaped configurations. The algorithm iterates through all possible positions for these cuts. For each potential partition, it calculates the area of the bounding box for the '1's within each of the three resulting rectangular regions. The sum of these three areas is a candidate for the minimum total area. By checking all possibilities, we can find the global minimum.

Algorithm

Implement a helper function getArea(r1, c1, r2, c2) that computes the area of the smallest bounding box covering all '1's within the subgrid from (r1, c1) to (r2, c2). This function iterates through all cells in the subgrid. If no '1's are found, it returns 0.
Initialize a variable minTotalArea to a very large value.
Systematically check all 6 ways to partition a rectangle into three smaller rectangles:
- Two vertical cuts: Iterate through all possible pairs of vertical cut lines, c1 and c2. This creates three vertical rectangular regions. Calculate the area for each region using getArea. If all three areas are non-zero, update minTotalArea with their sum.
- Two horizontal cuts: Similarly, iterate through all pairs of horizontal cut lines, r1 and r2, and do the same.
- Four T-shaped cuts: Iterate through a vertical cut c and a horizontal cut r. These two cuts divide the grid into four quadrants. By combining three of these quadrants in different ways, we can form four distinct T-shaped partitions. For each of these four configurations, calculate the areas of the three rectangles and update minTotalArea if they are all non-zero. The four configurations are: a. Left rectangle, top-right rectangle, bottom-right rectangle. b. Right rectangle, top-left rectangle, bottom-left rectangle. c. Top rectangle, bottom-left rectangle, bottom-right rectangle. d. Bottom rectangle, top-left rectangle, top-right rectangle.
After checking all possible partitions, minTotalArea will hold the minimum possible sum of areas.

Walkthrough

The core of this method is a helper function, getArea(r1, c1, r2, c2), which calculates the minimum bounding box area for all 1s within a specified rectangular subgrid. This function works by iterating through the cells of the subgrid to find the minimum and maximum row and column indices of the 1s.

The main logic then explores all six partitioning schemes:

Two Vertical Cuts: We use two nested loops to iterate through all possible positions for two vertical lines, c1 and c2. These lines divide the grid into three vertical strips: cols 0..c1-1, cols c1..c2-1, and cols c2..n-1. We calculate the area for each strip and sum them up.
Two Horizontal Cuts: This is analogous to the vertical case, but we iterate through two horizontal lines, r1 and r2, to create three horizontal strips.
T-Shaped Cuts: A T-shaped partition is formed by one main cut that spans the grid, and a second, perpendicular cut that splits one of the two resulting sub-rectangles. We can iterate through all possible intersection points (r, c) of a horizontal and a vertical line. This gives us four ways to form three rectangles (e.g., one rectangle on the left of c, and two rectangles on the right of c separated by r). We check all four such configurations for each (r, c) pair.

For every partition, we ensure that each of the three rectangles contains at least one '1' (has a non-zero area) before considering its total area as a potential minimum.

1class Solution {2    private int[][] grid;3    private int m, n;4 5    public int minimumArea(int[][] grid) {6        this.grid = grid;7        this.m = grid.length;8        this.n = grid[0].length;9        long minArea = Long.MAX_VALUE;10 11        // Case 1: Two vertical cuts12        for (int c1 = 1; c1 < n; c1++) {13            for (int c2 = c1 + 1; c2 < n; c2++) {14                long area1 = getArea(0, 0, m - 1, c1 - 1);15                long area2 = getArea(0, c1, m - 1, c2 - 1);16                long area3 = getArea(0, c2, m - 1, n - 1);17                if (area1 > 0 && area2 > 0 && area3 > 0) {18                    minArea = Math.min(minArea, area1 + area2 + area3);19                }20            }21        }22 23        // Case 2: Two horizontal cuts24        for (int r1 = 1; r1 < m; r1++) {25            for (int r2 = r1 + 1; r2 < m; r2++) {26                long area1 = getArea(0, 0, r1 - 1, n - 1);27                long area2 = getArea(r1, 0, r2 - 1, n - 1);28                long area3 = getArea(r2, 0, m - 1, n - 1);29                if (area1 > 0 && area2 > 0 && area3 > 0) {30                    minArea = Math.min(minArea, area1 + area2 + area3);31                }32            }33        }34 35        // Cases 3-6: T-shaped cuts36        for (int c = 1; c < n; c++) {37            for (int r = 1; r < m; r++) {38                // Config 1: Left, Top-Right, Bottom-Right39                long a1 = getArea(0, 0, m - 1, c - 1);40                long a2 = getArea(0, c, r - 1, n - 1);41                long a3 = getArea(r, c, m - 1, n - 1);42                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);43 44                // Config 2: Right, Top-Left, Bottom-Left45                a1 = getArea(0, c, m - 1, n - 1);46                a2 = getArea(0, 0, r - 1, c - 1);47                a3 = getArea(r, 0, m - 1, c - 1);48                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);49 50                // Config 3: Top, Bottom-Left, Bottom-Right51                a1 = getArea(0, 0, r - 1, n - 1);52                a2 = getArea(r, 0, m - 1, c - 1);53                a3 = getArea(r, c, m - 1, n - 1);54                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);55 56                // Config 4: Bottom, Top-Left, Top-Right57                a1 = getArea(r, 0, m - 1, n - 1);58                a2 = getArea(0, 0, r - 1, c - 1);59                a3 = getArea(0, c, r - 1, n - 1);60                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);61            }62        }63 64        return (int) minArea;65    }66 67    private long getArea(int r1, int c1, int r2, int c2) {68        int minR = m, maxR = -1, minC = n, maxC = -1;69        boolean foundOne = false;70        for (int i = r1; i <= r2; i++) {71            for (int j = c1; j <= c2; j++) {72                if (grid[i][j] == 1) {73                    foundOne = true;74                    minR = Math.min(minR, i);75                    maxR = Math.max(maxR, i);76                    minC = Math.min(minC, j);77                    maxC = Math.max(maxC, j);78                }79            }80        }81        if (!foundOne) return 0;82        return (long) (maxR - minR + 1) * (maxC - minC + 1);83    }84}

Complexity

Time

O(m^2 * n^2). The dominant part is handling the T-shaped cuts. There are O(m*n) possible cut intersections. For each, we call `getArea` three times. Each `getArea` call can take up to O(m*n) time in the worst case. This leads to a total complexity of O(m*n * m*n) = O(m^2 * n^2). The parallel cut cases have complexities of O(m*n^3) and O(n*m^3), which are lower for square-like grids.

Space

O(1) besides the input grid storage.

Trade-offs

Pros

Conceptually simple and easy to understand.
Guaranteed to find the correct answer because it checks all possible partition structures.

Cons

The time complexity is high due to redundant calculations.
The getArea function is called repeatedly for overlapping subgrids, leading to inefficiency.

This approach significantly optimizes the brute-force method by avoiding redundant calculations through precomputation and dynamic programming-like techniques. We first precompute the bounding box areas for all possible contiguous vertical and horizontal strips of the grid. This allows for O(1) area lookups for the parallel cut partitions. For the more complex T-shaped partitions, we iterate through the primary cut line. For each primary cut, instead of naively calculating the areas of the two smaller rectangles, we use an efficient method to find the optimal secondary cut, reducing the complexity for these cases as well.

Algorithm

Precomputation:
- Create a table areaCol[c1][c2] to store the bounding box area for all '1's in the vertical strip from column c1 to c2. This can be computed in O(m*n + n^2) time.
- Similarly, create areaRow[r1][r2] for horizontal strips in O(m*n + m^2) time.
Initialize minTotalArea to a very large value.
Case 1 & 2: Parallel cuts.
- For two vertical cuts, iterate through c1 and c2 (O(n^2) pairs). The total area is areaCol[0][c1-1] + areaCol[c1][c2-1] + areaCol[c2][n-1]. This is an O(1) lookup. Update minTotalArea.
- Do the same for two horizontal cuts using areaRow (O(m^2) iterations).
Case 3-6: T-shaped cuts.
- Consider the case with a primary vertical cut at c and a secondary horizontal cut at r (e.g., Left + Top-Right + Bottom-Right).
- Iterate through the primary cut c from 1 to n-1.
- The area of the first rectangle (e.g., the left part) is areaCol[0][c-1], which is a precomputed value.
- For the remaining part (e.g., the right part), we need to find the best horizontal split r. Instead of recomputing from scratch, we can efficiently calculate the areas of the top-right and bottom-right parts for all possible r's in O(m*n) time for a fixed c.
- For a fixed c, precompute topRightArea[r] (area of grid[0..r-1][c..n-1]) and bottomRightArea[r] (area of grid[r..m-1][c..n-1]) for all r.
- Then, iterate r from 1 to m-1 to find the minimum sum topRightArea[r] + bottomRightArea[r].
- Combine this minimum with the area of the first rectangle to update minTotalArea.
- Apply this optimized logic to all four T-shaped cut configurations.
Return minTotalArea.

Walkthrough

The main idea is to reduce the time spent inside the loops by pre-calculating necessary values.

Precomputation: First, we compute areaCol[c1][c2], the bounding box area for columns c1 to c2. We can do this in O(n^2) time after an initial O(m*n) scan to find the vertical extents of '1's in each column. Similarly, we compute areaRow[r1][r2] in O(m^2) time.

Partition Evaluation:

Parallel Cuts: With the precomputed tables, finding the minimum area for two parallel vertical cuts takes just O(n^2) time, as each partition's area is a sum of three O(1) table lookups. Similarly, horizontal cuts take O(m^2).
T-Shaped Cuts: Let's analyze one configuration: a vertical cut at c separating a left rectangle from a right part, which is then split horizontally at r. We iterate c from 1 to n-1. The area of the left rectangle is simply areaCol[0][c-1]. For the right part (grid[:, c:]), we need to find the best horizontal split r. We can do this efficiently. For the fixed c, we can compute an array topRightArea[r] (area for grid[0..r-1][c..n-1]) for all r in O(mn) time by incrementally building the bounding box. Similarly, we compute bottomRightArea[r] (area for grid[r..m-1][c..n-1]). Then, we iterate through r in O(m) to find the minimum sum topRightArea[r] + bottomRightArea[r]. The total time for this T-cut configuration becomes O(n * (mn + m)) = O(m*n^2). We apply the same logic to all T-cut cases.

This strategy reduces the overall complexity from O(m^2*n^2) to O(mn(m+n)), which is a significant improvement.

1class Solution {2    public int minimumArea(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5 6        long minArea = Long.MAX_VALUE;7 8        // Calculate areas for all vertical and horizontal strips9        long[][] areaCol = precomputeArea(grid, m, n, true);10        long[][] areaRow = precomputeArea(grid, m, n, false);11 12        // Case 1: Two vertical cuts13        for (int c1 = 1; c1 < n; c1++) {14            for (int c2 = c1 + 1; c2 < n; c2++) {15                long a1 = areaCol[0][c1 - 1];16                long a2 = areaCol[c1][c2 - 1];17                long a3 = areaCol[c2][n - 1];18                if (a1 > 0 && a2 > 0 && a3 > 0) {19                    minArea = Math.min(minArea, a1 + a2 + a3);20                }21            }22        }23 24        // Case 2: Two horizontal cuts25        for (int r1 = 1; r1 < m; r1++) {26            for (int r2 = r1 + 1; r2 < m; r2++) {27                long a1 = areaRow[0][r1 - 1];28                long a2 = areaRow[r1][r2 - 1];29                long a3 = areaRow[r2][m - 1];30                if (a1 > 0 && a2 > 0 && a3 > 0) {31                    minArea = Math.min(minArea, a1 + a2 + a3);32                }33            }34        }35 36        // Cases 3-6: T-shaped cuts37        for (int c = 1; c < n; c++) {38            long leftArea = areaCol[0][c - 1];39            long rightArea = areaCol[c][n - 1];40            long vSplitRight = minAreaFor2Rects(grid, 0, c, m - 1, n - 1, true);41            long vSplitLeft = minAreaFor2Rects(grid, 0, 0, m - 1, c - 1, true);42            if (leftArea > 0 && vSplitRight > 0) minArea = Math.min(minArea, leftArea + vSplitRight);43            if (rightArea > 0 && vSplitLeft > 0) minArea = Math.min(minArea, rightArea + vSplitLeft);44        }45 46        for (int r = 1; r < m; r++) {47            long topArea = areaRow[0][r - 1];48            long bottomArea = areaRow[r][m - 1];49            long hSplitBottom = minAreaFor2Rects(grid, r, 0, m - 1, n - 1, false);50            long hSplitTop = minAreaFor2Rects(grid, 0, 0, r - 1, n - 1, false);51            if (topArea > 0 && hSplitBottom > 0) minArea = Math.min(minArea, topArea + hSplitBottom);52            if (bottomArea > 0 && hSplitTop > 0) minArea = Math.min(minArea, bottomArea + hSplitTop);53        }54 55        return (int) minArea;56    }57 58    private long[][] precomputeArea(int[][] grid, int m, int n, boolean isVertical) {59        int dim1 = isVertical ? n : m;60        int dim2 = isVertical ? m : n;61        long[][] area = new long[dim1][dim1];62 63        for (int i = 0; i < dim1; i++) {64            int minR = dim2, maxR = -1, minC = dim1, maxC = -1;65            boolean hasOne = false;66            for (int j = i; j < dim1; j++) {67                int currentMinR = dim2, currentMaxR = -1;68                for (int k = 0; k < dim2; k++) {69                    if ((isVertical && grid[k][j] == 1) || (!isVertical && grid[j][k] == 1)) {70                        currentMinR = Math.min(currentMinR, k);71                        currentMaxR = Math.max(currentMaxR, k);72                    }73                }74                if (currentMaxR != -1) {75                    hasOne = true;76                    minR = Math.min(minR, currentMinR);77                    maxR = Math.max(maxR, currentMaxR);78                }79                if (hasOne) {80                    area[i][j] = (long)(maxR - minR + 1) * (j - i + 1);81                }82            }83        }84        return area;85    }86 87    private long minAreaFor2Rects(int[][] grid, int r1, int c1, int r2, int c2, boolean verticalSplit) {88        long minArea = Long.MAX_VALUE;89        if (verticalSplit) { // Split horizontally90            for (int r = r1 + 1; r <= r2; r++) {91                long a1 = getArea(grid, r1, c1, r - 1, c2);92                long a2 = getArea(grid, r, c1, r2, c2);93                if (a1 > 0 && a2 > 0) minArea = Math.min(minArea, a1 + a2);94            }95        } else { // Split vertically96            for (int c = c1 + 1; c <= c2; c++) {97                long a1 = getArea(grid, r1, c1, r2, c - 1);98                long a2 = getArea(grid, r1, c, r2, c2);99                if (a1 > 0 && a2 > 0) minArea = Math.min(minArea, a1 + a2);100            }101        }102        return minArea == Long.MAX_VALUE ? 0 : minArea;103    }104 105    private long getArea(int[][] grid, int r1, int c1, int r2, int c2) {106        int minR = grid.length, maxR = -1, minC = grid[0].length, maxC = -1;107        boolean foundOne = false;108        for (int i = r1; i <= r2; i++) {109            for (int j = c1; j <= c2; j++) {110                if (grid[i][j] == 1) {111                    foundOne = true;112                    minR = Math.min(minR, i);113                    maxR = Math.max(maxR, i);114                    minC = Math.min(minC, j);115                    maxC = Math.max(maxC, j);116                }117            }118        }119        if (!foundOne) return 0;120        return (long)(maxR - minR + 1) * (maxC - minC + 1);121    }122}

Complexity

Time

O(mn(m+n)). Precomputation takes O(m*n^2 + n*m^2). The parallel cut checks take O(m^2 + n^2). The T-cut checks take O(n * (m*n)) for vertical primary cuts and O(m * (m*n)) for horizontal primary cuts. The dominant part is the T-cut evaluation, leading to a total complexity of O(m*n^2 + n*m^2).

Space

O(m^2 + n^2) to store the precomputed area tables for horizontal and vertical strips.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Handles the given constraints (m, n <= 30) very quickly.

Cons

More complex to implement due to precomputation steps and more intricate loop structures.
Requires additional space for the precomputed tables.

Solutions

Solution

1class Solution {2private3  final int inf = 1 << 30;4private5  int[][] grid;6public7  int minimumSum(int[][] grid) {8    this.grid = grid;9    int m = grid.length;10    int n = grid[0].length;11    int ans = m * n;12    for (int i1 = 0; i1 < m - 1; i1++) {13      for (int i2 = i1 + 1; i2 < m - 1; i2++) {14        ans = Math.min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) +15                                f(i2 + 1, 0, m - 1, n - 1));16      }17    }18    for (int j1 = 0; j1 < n - 1; j1++) {19      for (int j2 = j1 + 1; j2 < n - 1; j2++) {20        ans = Math.min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) +21                                f(0, j2 + 1, m - 1, n - 1));22      }23    }24    for (int i = 0; i < m - 1; i++) {25      for (int j = 0; j < n - 1; j++) {26        ans = Math.min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) +27                                f(i + 1, 0, m - 1, n - 1));28        ans = Math.min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) +29                                f(i + 1, j + 1, m - 1, n - 1));30        ans = Math.min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) +31                                f(0, j + 1, m - 1, n - 1));32        ans = Math.min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) +33                                f(i + 1, j + 1, m - 1, n - 1));34      }35    }36    return ans;37  }38private39  int f(int i1, int j1, int i2, int j2) {40    int x1 = inf, y1 = inf;41    int x2 = -inf, y2 = -inf;42    for (int i = i1; i <= i2; i++) {43      for (int j = j1; j <= j2; j++) {44        if (grid[i][j] == 1) {45          x1 = Math.min(x1, i);46          y1 = Math.min(y1, j);47          x2 = Math.max(x2, i);48          y2 = Math.max(y2, j);49        }50      }51    }52    return (x2 - x1 + 1) * (y2 - y1 + 1);53  }54}

1class Solution {2public:3  int minimumSum(vector<vector<int>> &grid) {4    int m = grid.size();5    int n = grid[0].size();6    int ans = m * n;7    int inf = INT_MAX / 4;8    auto f = [&](int i1, int j1, int i2, int j2) {9      int x1 = inf, y1 = inf;10      int x2 = -inf, y2 = -inf;11      for (int i = i1; i <= i2; i++) {12        for (int j = j1; j <= j2; j++) {13          if (grid[i][j] == 1) {14            x1 = min(x1, i);15            y1 = min(y1, j);16            x2 = max(x2, i);17            y2 = max(y2, j);18          }19        }20      }21      return x1 > x2 || y1 > y2 ? inf : (x2 - x1 + 1) * (y2 - y1 + 1);22    };23    for (int i1 = 0; i1 < m - 1; i1++) {24      for (int i2 = i1 + 1; i2 < m - 1; i2++) {25        ans = min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) +26                           f(i2 + 1, 0, m - 1, n - 1));27      }28    }29    for (int j1 = 0; j1 < n - 1; j1++) {30      for (int j2 = j1 + 1; j2 < n - 1; j2++) {31        ans = min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) +32                           f(0, j2 + 1, m - 1, n - 1));33      }34    }35    for (int i = 0; i < m - 1; i++) {36      for (int j = 0; j < n - 1; j++) {37        ans = min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) +38                           f(i + 1, 0, m - 1, n - 1));39        ans = min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) +40                           f(i + 1, j + 1, m - 1, n - 1));41        ans = min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) +42                           f(0, j + 1, m - 1, n - 1));43        ans = min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) +44                           f(i + 1, j + 1, m - 1, n - 1));45      }46    }47    return ans;48  }49};

1class Solution:2    def minimumSum(self, grid: List[List[int]]) -> int: def f(i1: int, j1: int, i2: int, j2: int) -> int: x1 = y1 = inf x2 = y2 = - inf for i in range(i1, i2 + 1): for j in range(j1, j2 + 1): if grid[i][j] == 1: x1 = min(x1, i) y1 = min(y1, j) x2 = max(x2, i) y2 = max(y2, j) return (x2 - x1 + 1) * (y2 - y1 + 1) m, n = len(grid), len(grid[0]) ans = m * n for i1 in range(m - 1): for i2 in range(i1 + 1, m - 1): ans = min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) + f(i2 + 1, 0, m - 1, n - 1), ) for j1 in range(n - 1): for j2 in range(j1 + 1, n - 1): ans = min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) + f(0, j2 + 1, m - 1, n - 1), ) for i in range(m - 1): for j in range(n - 1): ans = min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) + f(i + 1, 0, m - 1, n - 1), ) ans = min(ans, f(0, 0, i, n - 1) + f(i + 1, 0, m - 1, j) + f(i + 1, j + 1, m - 1, n - 1), ) ans = min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) + f(0, j + 1, m - 1, n - 1), ) ans = min(ans, f(0, 0, m - 1, j) + f(0, j + 1, i, n - 1) + f(i + 1, j + 1, m - 1, n - 1), ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem