Scale Engineer

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
ArrayMatrix

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

  1. 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.
  2. Initialize a variable minTotalArea to a very large value.
  3. 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.
  4. 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:

  1. 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.

  2. 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.

  3. 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.

class Solution {    private int[][] grid;    private int m, n;     public int minimumArea(int[][] grid) {        this.grid = grid;        this.m = grid.length;        this.n = grid[0].length;        long minArea = Long.MAX_VALUE;         // Case 1: Two vertical cuts        for (int c1 = 1; c1 < n; c1++) {            for (int c2 = c1 + 1; c2 < n; c2++) {                long area1 = getArea(0, 0, m - 1, c1 - 1);                long area2 = getArea(0, c1, m - 1, c2 - 1);                long area3 = getArea(0, c2, m - 1, n - 1);                if (area1 > 0 && area2 > 0 && area3 > 0) {                    minArea = Math.min(minArea, area1 + area2 + area3);                }            }        }         // Case 2: Two horizontal cuts        for (int r1 = 1; r1 < m; r1++) {            for (int r2 = r1 + 1; r2 < m; r2++) {                long area1 = getArea(0, 0, r1 - 1, n - 1);                long area2 = getArea(r1, 0, r2 - 1, n - 1);                long area3 = getArea(r2, 0, m - 1, n - 1);                if (area1 > 0 && area2 > 0 && area3 > 0) {                    minArea = Math.min(minArea, area1 + area2 + area3);                }            }        }         // Cases 3-6: T-shaped cuts        for (int c = 1; c < n; c++) {            for (int r = 1; r < m; r++) {                // Config 1: Left, Top-Right, Bottom-Right                long a1 = getArea(0, 0, m - 1, c - 1);                long a2 = getArea(0, c, r - 1, n - 1);                long a3 = getArea(r, c, m - 1, n - 1);                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);                 // Config 2: Right, Top-Left, Bottom-Left                a1 = getArea(0, c, m - 1, n - 1);                a2 = getArea(0, 0, r - 1, c - 1);                a3 = getArea(r, 0, m - 1, c - 1);                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);                 // Config 3: Top, Bottom-Left, Bottom-Right                a1 = getArea(0, 0, r - 1, n - 1);                a2 = getArea(r, 0, m - 1, c - 1);                a3 = getArea(r, c, m - 1, n - 1);                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);                 // Config 4: Bottom, Top-Left, Top-Right                a1 = getArea(r, 0, m - 1, n - 1);                a2 = getArea(0, 0, r - 1, c - 1);                a3 = getArea(0, c, r - 1, n - 1);                if (a1 > 0 && a2 > 0 && a3 > 0) minArea = Math.min(minArea, a1 + a2 + a3);            }        }         return (int) minArea;    }     private long getArea(int r1, int c1, int r2, int c2) {        int minR = m, maxR = -1, minC = n, maxC = -1;        boolean foundOne = false;        for (int i = r1; i <= r2; i++) {            for (int j = c1; j <= c2; j++) {                if (grid[i][j] == 1) {                    foundOne = true;                    minR = Math.min(minR, i);                    maxR = Math.max(maxR, i);                    minC = Math.min(minC, j);                    maxC = Math.max(maxC, j);                }            }        }        if (!foundOne) return 0;        return (long) (maxR - minR + 1) * (maxC - minC + 1);    }}

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.

Solutions

class Solution {private  final int inf = 1 << 30;private  int[][] grid;public  int minimumSum(int[][] grid) {    this.grid = grid;    int m = grid.length;    int n = grid[0].length;    int ans = m * n;    for (int i1 = 0; i1 < m - 1; i1++) {      for (int i2 = i1 + 1; i2 < m - 1; i2++) {        ans = Math.min(ans, f(0, 0, i1, n - 1) + f(i1 + 1, 0, i2, n - 1) +                                f(i2 + 1, 0, m - 1, n - 1));      }    }    for (int j1 = 0; j1 < n - 1; j1++) {      for (int j2 = j1 + 1; j2 < n - 1; j2++) {        ans = Math.min(ans, f(0, 0, m - 1, j1) + f(0, j1 + 1, m - 1, j2) +                                f(0, j2 + 1, m - 1, n - 1));      }    }    for (int i = 0; i < m - 1; i++) {      for (int j = 0; j < n - 1; j++) {        ans = Math.min(ans, f(0, 0, i, j) + f(0, j + 1, i, n - 1) +                                f(i + 1, 0, m - 1, n - 1));        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));        ans = Math.min(ans, f(0, 0, i, j) + f(i + 1, 0, m - 1, j) +                                f(0, j + 1, m - 1, n - 1));        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));      }    }    return ans;  }private  int f(int i1, int j1, int i2, int j2) {    int x1 = inf, y1 = inf;    int x2 = -inf, y2 = -inf;    for (int i = i1; i <= i2; i++) {      for (int j = j1; j <= j2; j++) {        if (grid[i][j] == 1) {          x1 = Math.min(x1, i);          y1 = Math.min(y1, j);          x2 = Math.max(x2, i);          y2 = Math.max(y2, j);        }      }    }    return (x2 - x1 + 1) * (y2 - y1 + 1);  }}

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 →

Next problem