Facebook Pixel

3197. Find the Minimum Area to Cover All Ones II

HardArrayEnumerationMatrix
Leetcode Link

Problem Description

You have a 2D binary array grid containing only 0s and 1s. Your task is to find 3 non-overlapping rectangles that cover all the 1s in the grid. These rectangles must have non-zero areas and their sides must be horizontal and vertical (aligned with the grid axes).

The goal is to minimize the total sum of the areas of these three rectangles. The rectangles can touch each other at their boundaries but cannot overlap.

Each rectangle's area is calculated as (height) × (width), where the height and width are determined by the minimum bounding box that contains all the 1s assigned to that rectangle.

The solution approach involves trying different ways to partition the grid into three regions:

  • Using two horizontal dividing lines to create three horizontal strips
  • Using two vertical dividing lines to create three vertical strips
  • Using one horizontal line followed by one vertical line (creating an L-shape and two rectangles)
  • Using one vertical line followed by one horizontal line (creating different L-shape configurations)

For each partition configuration, the algorithm calculates the minimum bounding rectangle for the 1s in each region using the helper function f(i1, j1, i2, j2), which finds the tightest rectangle containing all 1s in the subgrid from position (i1, j1) to (i2, j2).

The answer is the minimum sum across all possible valid partitions of the grid into three rectangles.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that to divide a grid into exactly 3 non-overlapping rectangles, we need exactly 2 cuts. These cuts can be made in different patterns, and we want to find the pattern that minimizes the total area.

Think about it geometrically - when we need to split a rectangle into 3 parts, there are only a limited number of ways to do this:

  1. Make two parallel cuts (either both horizontal or both vertical), creating 3 strips
  2. Make one cut in one direction, then make another cut perpendicular to the first one, but only through one of the resulting pieces

Why does this work? Because once we assign each 1 in the grid to one of the three rectangles, each rectangle needs to be sized just large enough to contain all its assigned 1s. The minimum bounding box for a set of points is uniquely determined - it's the smallest rectangle with sides parallel to the axes that contains all the points.

The challenge is that we don't know in advance which 1s should belong to which rectangle. However, by trying all possible ways to partition the grid into three regions using straight cuts, we guarantee that we'll find the optimal assignment. Each partition uniquely determines which 1s belong to which rectangle.

For each partition pattern, we enumerate all possible positions for the cuts. For example, with two horizontal cuts, we try all pairs of row indices (i1, i2) where i1 < i2. This ensures we don't miss the optimal solution.

The function f(i1, j1, i2, j2) efficiently computes the area of the minimum bounding rectangle for all 1s in a given subgrid by finding the minimum and maximum row and column indices containing a 1, then calculating (x2 - x1 + 1) * (y2 - y1 + 1).

By exhaustively checking all 6 partition patterns and all possible cut positions within each pattern, we're guaranteed to find the configuration that minimizes the sum of the three rectangular areas.

Solution Approach

The solution implements a brute-force approach that systematically tries all possible ways to partition the grid into three rectangles.

Helper Function f(i1, j1, i2, j2): This function calculates the minimum bounding rectangle area for all 1s in the subgrid from (i1, j1) to (i2, j2):

  • Initialize bounds: x1 = y1 = inf (minimum coordinates) and x2 = y2 = -inf (maximum coordinates)
  • Scan through the subgrid to find all cells containing 1
  • Update the bounds to track the minimum and maximum row/column indices where 1s appear
  • Return the area as (x2 - x1 + 1) * (y2 - y1 + 1)

Main Algorithm: The solution enumerates all 6 partition patterns:

  1. Two Horizontal Splits:

    • Use two row indices i1 and i2 where i1 < i2
    • Create three horizontal strips: [0, i1], [i1+1, i2], [i2+1, m-1]
    • Calculate: f(0, 0, i1, n-1) + f(i1+1, 0, i2, n-1) + f(i2+1, 0, m-1, n-1)

  2. Two Vertical Splits:

    • Use two column indices j1 and j2 where j1 < j2
    • Create three vertical strips: [0, j1], [j1+1, j2], [j2+1, n-1]
    • Calculate: f(0, 0, m-1, j1) + f(0, j1+1, m-1, j2) + f(0, j2+1, m-1, n-1)

  3. L-shaped Partitions: For each position (i, j), try 4 different L-shaped configurations:

    • Top-left L: Split horizontally at row i, then split the top part vertically at column j
      • Rectangles: top-left [0,0,i,j], top-right [0,j+1,i,n-1], bottom [i+1,0,m-1,n-1]
    • Bottom-left L: Split horizontally at row i, then split the bottom part vertically at column j
      • Rectangles: top [0,0,i,n-1], bottom-left [i+1,0,m-1,j], bottom-right [i+1,j+1,m-1,n-1]
    • Top-right L: Split vertically at column j, then split the left part horizontally at row i
      • Rectangles: top-left [0,0,i,j], bottom-left [i+1,0,m-1,j], right [0,j+1,m-1,n-1]
    • Bottom-right L: Split vertically at column j, then split the right part horizontally at row i
      • Rectangles: left [0,0,m-1,j], top-right [0,j+1,i,n-1], bottom-right [i+1,j+1,m-1,n-1]

Optimization:

  • Initialize ans with m * n (the maximum possible area)
  • For each valid partition, calculate the sum of the three rectangle areas
  • Update ans with the minimum sum found

The algorithm has time complexity of O(m²n² × mn) where the m²n² comes from enumerating all possible cut positions and mn from computing each rectangle's bounding box.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

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

Consider this 4×4 grid:

1 1 0 0
1 0 0 0
0 0 1 1
0 0 1 0

We need to find 3 non-overlapping rectangles that cover all the 1s with minimum total area.

Step 1: Try Two Horizontal Splits

Let's try splitting at rows i1=1 and i2=2:

  • Top strip (rows 0-1): Contains 1s at (0,0), (0,1), (1,0)
    • Minimum bounding box: from (0,0) to (1,1) → area = 2×2 = 4
  • Middle strip (row 2): Contains 1s at (2,2), (2,3)
    • Minimum bounding box: from (2,2) to (2,3) → area = 1×2 = 2
  • Bottom strip (row 3): Contains 1 at (3,2)
    • Minimum bounding box: from (3,2) to (3,2) → area = 1×1 = 1
  • Total area = 4 + 2 + 1 = 7

Step 2: Try Two Vertical Splits

Let's try splitting at columns j1=1 and j2=2:

  • Left strip (columns 0-1): Contains 1s at (0,0), (0,1), (1,0)
    • Minimum bounding box: from (0,0) to (1,1) → area = 2×2 = 4
  • Middle strip (column 2): Contains 1s at (2,2), (3,2)
    • Minimum bounding box: from (2,2) to (3,2) → area = 2×1 = 2
  • Right strip (column 3): Contains 1 at (2,3)
    • Minimum bounding box: from (2,3) to (2,3) → area = 1×1 = 1
  • Total area = 4 + 2 + 1 = 7

Step 3: Try L-shaped Partition

Let's try a top-left L configuration with horizontal split at row i=1 and vertical split at column j=1:

  • Top-left rectangle (rows 0-1, columns 0-1): Contains 1s at (0,0), (0,1), (1,0)
    • Minimum bounding box: from (0,0) to (1,1) → area = 2×2 = 4
  • Top-right rectangle (rows 0-1, columns 2-3): No 1s
    • No valid bounding box → area = 0 (invalid partition)
  • Bottom rectangle (rows 2-3, columns 0-3): Contains 1s at (2,2), (2,3), (3,2)
    • Minimum bounding box: from (2,2) to (3,3) → area = 2×2 = 4

This partition is invalid because one rectangle contains no 1s.

Step 4: Try Another L-shaped Partition

Let's try a bottom-left L with horizontal split at row i=1 and vertical split at column j=1:

  • Top rectangle (rows 0-1, columns 0-3): Contains 1s at (0,0), (0,1), (1,0)
    • Minimum bounding box: from (0,0) to (1,1) → area = 2×2 = 4
  • Bottom-left rectangle (rows 2-3, columns 0-1): No 1s
    • Invalid partition (no 1s in this rectangle)
  • Bottom-right rectangle (rows 2-3, columns 2-3): Contains 1s at (2,2), (2,3), (3,2)
    • Minimum bounding box: from (2,2) to (3,3) → area = 2×2 = 4

Also invalid.

Step 5: Finding a Valid L-shaped Partition

Let's try horizontal split at i=1, vertical split at j=2 in bottom-left L configuration:

  • Top rectangle (rows 0-1, columns 0-3): Contains 1s at (0,0), (0,1), (1,0)
    • Minimum bounding box: from (0,0) to (1,1) → area = 2×2 = 4
  • Bottom-left rectangle (rows 2-3, columns 0-2): Contains 1s at (2,2), (3,2)
    • Minimum bounding box: from (2,2) to (3,2) → area = 2×1 = 2
  • Bottom-right rectangle (rows 2-3, column 3): Contains 1 at (2,3)
    • Minimum bounding box: from (2,3) to (2,3) → area = 1×1 = 1
  • Total area = 4 + 2 + 1 = 7

After trying all possible partitions, the minimum total area found is 7. The algorithm returns this as the answer.

Solution Implementation

1class Solution:
2    def minimumSum(self, grid: List[List[int]]) -> int:
3        def calculate_rectangle_area(row1: int, col1: int, row2: int, col2: int) -> int:
4            """
5            Calculate the area of the minimum bounding rectangle that contains all 1s
6            in the subgrid from (row1, col1) to (row2, col2).
7          
8            Args:
9                row1, col1: Top-left corner of the subgrid
10                row2, col2: Bottom-right corner of the subgrid
11          
12            Returns:
13                Area of the minimum bounding rectangle containing all 1s
14            """
15            # Initialize bounds for the minimum bounding rectangle
16            min_row = float('inf')
17            min_col = float('inf')
18            max_row = -float('inf')
19            max_col = -float('inf')
20          
21            # Find the bounds of all cells containing 1
22            for row in range(row1, row2 + 1):
23                for col in range(col1, col2 + 1):
24                    if grid[row][col] == 1:
25                        min_row = min(min_row, row)
26                        min_col = min(min_col, col)
27                        max_row = max(max_row, row)
28                        max_col = max(max_col, col)
29          
30            # Calculate and return the area of the bounding rectangle
31            return (max_row - min_row + 1) * (max_col - min_col + 1)
32      
33        rows, cols = len(grid), len(grid[0])
34        min_total_area = rows * cols
35      
36        # Case 1: Three horizontal strips
37        # Divide the grid into three horizontal rectangles
38        for row1 in range(rows - 1):
39            for row2 in range(row1 + 1, rows - 1):
40                total_area = (
41                    calculate_rectangle_area(0, 0, row1, cols - 1) +
42                    calculate_rectangle_area(row1 + 1, 0, row2, cols - 1) +
43                    calculate_rectangle_area(row2 + 1, 0, rows - 1, cols - 1)
44                )
45                min_total_area = min(min_total_area, total_area)
46      
47        # Case 2: Three vertical strips
48        # Divide the grid into three vertical rectangles
49        for col1 in range(cols - 1):
50            for col2 in range(col1 + 1, cols - 1):
51                total_area = (
52                    calculate_rectangle_area(0, 0, rows - 1, col1) +
53                    calculate_rectangle_area(0, col1 + 1, rows - 1, col2) +
54                    calculate_rectangle_area(0, col2 + 1, rows - 1, cols - 1)
55                )
56                min_total_area = min(min_total_area, total_area)
57      
58        # Case 3-6: Mixed divisions (one horizontal and one vertical cut)
59        for row in range(rows - 1):
60            for col in range(cols - 1):
61                # Configuration 1: Top-left, top-right, bottom
62                total_area = (
63                    calculate_rectangle_area(0, 0, row, col) +
64                    calculate_rectangle_area(0, col + 1, row, cols - 1) +
65                    calculate_rectangle_area(row + 1, 0, rows - 1, cols - 1)
66                )
67                min_total_area = min(min_total_area, total_area)
68              
69                # Configuration 2: Top, bottom-left, bottom-right
70                total_area = (
71                    calculate_rectangle_area(0, 0, row, cols - 1) +
72                    calculate_rectangle_area(row + 1, 0, rows - 1, col) +
73                    calculate_rectangle_area(row + 1, col + 1, rows - 1, cols - 1)
74                )
75                min_total_area = min(min_total_area, total_area)
76              
77                # Configuration 3: Top-left, bottom-left, right
78                total_area = (
79                    calculate_rectangle_area(0, 0, row, col) +
80                    calculate_rectangle_area(row + 1, 0, rows - 1, col) +
81                    calculate_rectangle_area(0, col + 1, rows - 1, cols - 1)
82                )
83                min_total_area = min(min_total_area, total_area)
84              
85                # Configuration 4: Left, top-right, bottom-right
86                total_area = (
87                    calculate_rectangle_area(0, 0, rows - 1, col) +
88                    calculate_rectangle_area(0, col + 1, row, cols - 1) +
89                    calculate_rectangle_area(row + 1, col + 1, rows - 1, cols - 1)
90                )
91                min_total_area = min(min_total_area, total_area)
92      
93        return min_total_area
94
1class Solution {
2    private final int INFINITY = 1 << 30;
3    private int[][] grid;
4
5    /**
6     * Finds the minimum sum of areas of exactly 3 non-overlapping rectangles
7     * that cover all cells with value 1 in the grid.
8     * 
9     * @param grid 2D array containing 0s and 1s
10     * @return minimum sum of areas of 3 rectangles covering all 1s
11     */
12    public int minimumSum(int[][] grid) {
13        this.grid = grid;
14        int rows = grid.length;
15        int cols = grid[0].length;
16        int minArea = rows * cols;
17
18        // Case 1: Three horizontal strips
19        // Divide the grid using two horizontal lines
20        for (int firstDivider = 0; firstDivider < rows - 1; firstDivider++) {
21            for (int secondDivider = firstDivider + 1; secondDivider < rows - 1; secondDivider++) {
22                int topRectangle = calculateMinimumRectangleArea(0, 0, firstDivider, cols - 1);
23                int middleRectangle = calculateMinimumRectangleArea(firstDivider + 1, 0, secondDivider, cols - 1);
24                int bottomRectangle = calculateMinimumRectangleArea(secondDivider + 1, 0, rows - 1, cols - 1);
25                minArea = Math.min(minArea, topRectangle + middleRectangle + bottomRectangle);
26            }
27        }
28
29        // Case 2: Three vertical strips
30        // Divide the grid using two vertical lines
31        for (int firstDivider = 0; firstDivider < cols - 1; firstDivider++) {
32            for (int secondDivider = firstDivider + 1; secondDivider < cols - 1; secondDivider++) {
33                int leftRectangle = calculateMinimumRectangleArea(0, 0, rows - 1, firstDivider);
34                int middleRectangle = calculateMinimumRectangleArea(0, firstDivider + 1, rows - 1, secondDivider);
35                int rightRectangle = calculateMinimumRectangleArea(0, secondDivider + 1, rows - 1, cols - 1);
36                minArea = Math.min(minArea, leftRectangle + middleRectangle + rightRectangle);
37            }
38        }
39
40        // Case 3: Mixed divisions (one horizontal and one vertical line)
41        for (int horizontalDivider = 0; horizontalDivider < rows - 1; horizontalDivider++) {
42            for (int verticalDivider = 0; verticalDivider < cols - 1; verticalDivider++) {
43                // Configuration 1: Top-left, top-right, bottom
44                int topLeft = calculateMinimumRectangleArea(0, 0, horizontalDivider, verticalDivider);
45                int topRight = calculateMinimumRectangleArea(0, verticalDivider + 1, horizontalDivider, cols - 1);
46                int bottom = calculateMinimumRectangleArea(horizontalDivider + 1, 0, rows - 1, cols - 1);
47                minArea = Math.min(minArea, topLeft + topRight + bottom);
48
49                // Configuration 2: Top, bottom-left, bottom-right
50                int top = calculateMinimumRectangleArea(0, 0, horizontalDivider, cols - 1);
51                int bottomLeft = calculateMinimumRectangleArea(horizontalDivider + 1, 0, rows - 1, verticalDivider);
52                int bottomRight = calculateMinimumRectangleArea(horizontalDivider + 1, verticalDivider + 1, rows - 1, cols - 1);
53                minArea = Math.min(minArea, top + bottomLeft + bottomRight);
54
55                // Configuration 3: Top-left, bottom-left, right
56                topLeft = calculateMinimumRectangleArea(0, 0, horizontalDivider, verticalDivider);
57                bottomLeft = calculateMinimumRectangleArea(horizontalDivider + 1, 0, rows - 1, verticalDivider);
58                int right = calculateMinimumRectangleArea(0, verticalDivider + 1, rows - 1, cols - 1);
59                minArea = Math.min(minArea, topLeft + bottomLeft + right);
60
61                // Configuration 4: Left, top-right, bottom-right
62                int left = calculateMinimumRectangleArea(0, 0, rows - 1, verticalDivider);
63                topRight = calculateMinimumRectangleArea(0, verticalDivider + 1, horizontalDivider, cols - 1);
64                bottomRight = calculateMinimumRectangleArea(horizontalDivider + 1, verticalDivider + 1, rows - 1, cols - 1);
65                minArea = Math.min(minArea, left + topRight + bottomRight);
66            }
67        }
68      
69        return minArea;
70    }
71
72    /**
73     * Calculates the minimum area of a rectangle that covers all 1s 
74     * in the specified sub-region of the grid.
75     * 
76     * @param row1 starting row (inclusive)
77     * @param col1 starting column (inclusive)
78     * @param row2 ending row (inclusive)
79     * @param col2 ending column (inclusive)
80     * @return area of the minimum bounding rectangle for all 1s in the sub-region
81     */
82    private int calculateMinimumRectangleArea(int row1, int col1, int row2, int col2) {
83        // Initialize bounds for minimum bounding rectangle
84        int minRow = INFINITY, minCol = INFINITY;
85        int maxRow = -INFINITY, maxCol = -INFINITY;
86      
87        // Find the bounds of all cells containing 1
88        for (int row = row1; row <= row2; row++) {
89            for (int col = col1; col <= col2; col++) {
90                if (grid[row][col] == 1) {
91                    minRow = Math.min(minRow, row);
92                    minCol = Math.min(minCol, col);
93                    maxRow = Math.max(maxRow, row);
94                    maxCol = Math.max(maxCol, col);
95                }
96            }
97        }
98      
99        // Calculate and return the area of the bounding rectangle
100        return (maxRow - minRow + 1) * (maxCol - minCol + 1);
101    }
102}
103
1class Solution {
2public:
3    int minimumSum(vector<vector<int>>& grid) {
4        int rows = grid.size();
5        int cols = grid[0].size();
6        int minArea = rows * cols;  // Initialize with maximum possible area
7        int INF = INT_MAX / 4;  // Large value to represent invalid rectangles
8      
9        // Lambda function to calculate the minimum bounding rectangle area for a subgrid
10        // Parameters: (row1, col1) = top-left corner, (row2, col2) = bottom-right corner
11        auto calculateRectangleArea = [&](int row1, int col1, int row2, int col2) {
12            int minRow = INF, minCol = INF;  // Track minimum row and column with 1
13            int maxRow = -INF, maxCol = -INF;  // Track maximum row and column with 1
14          
15            // Find the bounding box of all 1s in the specified subgrid
16            for (int i = row1; i <= row2; i++) {
17                for (int j = col1; j <= col2; j++) {
18                    if (grid[i][j] == 1) {
19                        minRow = min(minRow, i);
20                        minCol = min(minCol, j);
21                        maxRow = max(maxRow, i);
22                        maxCol = max(maxCol, j);
23                    }
24                }
25            }
26          
27            // If no 1s found (minRow > maxRow), return INF; otherwise return bounding box area
28            return (minRow > maxRow || minCol > maxCol) ? INF : 
29                   (maxRow - minRow + 1) * (maxCol - minCol + 1);
30        };
31
32        // Case 1: Divide grid with two horizontal lines (creating 3 horizontal strips)
33        for (int firstDivider = 0; firstDivider < rows - 1; firstDivider++) {
34            for (int secondDivider = firstDivider + 1; secondDivider < rows - 1; secondDivider++) {
35                int topArea = calculateRectangleArea(0, 0, firstDivider, cols - 1);
36                int middleArea = calculateRectangleArea(firstDivider + 1, 0, secondDivider, cols - 1);
37                int bottomArea = calculateRectangleArea(secondDivider + 1, 0, rows - 1, cols - 1);
38                minArea = min(minArea, topArea + middleArea + bottomArea);
39            }
40        }
41
42        // Case 2: Divide grid with two vertical lines (creating 3 vertical strips)
43        for (int firstDivider = 0; firstDivider < cols - 1; firstDivider++) {
44            for (int secondDivider = firstDivider + 1; secondDivider < cols - 1; secondDivider++) {
45                int leftArea = calculateRectangleArea(0, 0, rows - 1, firstDivider);
46                int middleArea = calculateRectangleArea(0, firstDivider + 1, rows - 1, secondDivider);
47                int rightArea = calculateRectangleArea(0, secondDivider + 1, rows - 1, cols - 1);
48                minArea = min(minArea, leftArea + middleArea + rightArea);
49            }
50        }
51
52        // Case 3: Divide grid with one horizontal and one vertical line (creating various T-shapes)
53        for (int horizontalDivider = 0; horizontalDivider < rows - 1; horizontalDivider++) {
54            for (int verticalDivider = 0; verticalDivider < cols - 1; verticalDivider++) {
55                // T-shape with horizontal bar on top
56                int topLeft = calculateRectangleArea(0, 0, horizontalDivider, verticalDivider);
57                int topRight = calculateRectangleArea(0, verticalDivider + 1, horizontalDivider, cols - 1);
58                int bottom = calculateRectangleArea(horizontalDivider + 1, 0, rows - 1, cols - 1);
59                minArea = min(minArea, topLeft + topRight + bottom);
60              
61                // T-shape with horizontal bar on bottom
62                int top = calculateRectangleArea(0, 0, horizontalDivider, cols - 1);
63                int bottomLeft = calculateRectangleArea(horizontalDivider + 1, 0, rows - 1, verticalDivider);
64                int bottomRight = calculateRectangleArea(horizontalDivider + 1, verticalDivider + 1, rows - 1, cols - 1);
65                minArea = min(minArea, top + bottomLeft + bottomRight);
66              
67                // T-shape with vertical bar on left
68                topLeft = calculateRectangleArea(0, 0, horizontalDivider, verticalDivider);
69                bottomLeft = calculateRectangleArea(horizontalDivider + 1, 0, rows - 1, verticalDivider);
70                int right = calculateRectangleArea(0, verticalDivider + 1, rows - 1, cols - 1);
71                minArea = min(minArea, topLeft + bottomLeft + right);
72              
73                // T-shape with vertical bar on right
74                int left = calculateRectangleArea(0, 0, rows - 1, verticalDivider);
75                topRight = calculateRectangleArea(0, verticalDivider + 1, horizontalDivider, cols - 1);
76                bottomRight = calculateRectangleArea(horizontalDivider + 1, verticalDivider + 1, rows - 1, cols - 1);
77                minArea = min(minArea, left + topRight + bottomRight);
78            }
79        }
80
81        return minArea;
82    }
83};
84
1/**
2 * Finds the minimum sum of areas of three non-overlapping rectangles that cover all 1s in the grid
3 * @param grid - 2D array containing 0s and 1s
4 * @returns The minimum sum of areas of three rectangles
5 */
6function minimumSum(grid: number[][]): number {
7    const rows: number = grid.length;
8    const cols: number = grid[0].length;
9    let minArea: number = rows * cols;
10    const INFINITY: number = Number.MAX_SAFE_INTEGER;
11  
12    /**
13     * Calculates the area of the smallest rectangle that covers all 1s in a subgrid
14     * @param row1 - Starting row index (inclusive)
15     * @param col1 - Starting column index (inclusive)
16     * @param row2 - Ending row index (inclusive)
17     * @param col2 - Ending column index (inclusive)
18     * @returns Area of the smallest rectangle covering all 1s, or 0 if no 1s exist
19     */
20    const calculateRectangleArea = (row1: number, col1: number, row2: number, col2: number): number => {
21        // Initialize bounds for the smallest rectangle
22        let minRow: number = INFINITY;
23        let minCol: number = INFINITY;
24        let maxRow: number = -INFINITY;
25        let maxCol: number = -INFINITY;
26      
27        // Find the bounds of all 1s in the subgrid
28        for (let i = row1; i <= row2; i++) {
29            for (let j = col1; j <= col2; j++) {
30                if (grid[i][j] === 1) {
31                    minRow = Math.min(minRow, i);
32                    minCol = Math.min(minCol, j);
33                    maxRow = Math.max(maxRow, i);
34                    maxCol = Math.max(maxCol, j);
35                }
36            }
37        }
38      
39        // Return 0 if no 1s found, otherwise return the area
40        return minRow === INFINITY ? 0 : (maxRow - minRow + 1) * (maxCol - minCol + 1);
41    };
42
43    // Try dividing the grid with two horizontal cuts
44    for (let firstCut = 0; firstCut < rows - 1; firstCut++) {
45        for (let secondCut = firstCut + 1; secondCut < rows - 1; secondCut++) {
46            const topArea: number = calculateRectangleArea(0, 0, firstCut, cols - 1);
47            const middleArea: number = calculateRectangleArea(firstCut + 1, 0, secondCut, cols - 1);
48            const bottomArea: number = calculateRectangleArea(secondCut + 1, 0, rows - 1, cols - 1);
49            minArea = Math.min(minArea, topArea + middleArea + bottomArea);
50        }
51    }
52
53    // Try dividing the grid with two vertical cuts
54    for (let firstCut = 0; firstCut < cols - 1; firstCut++) {
55        for (let secondCut = firstCut + 1; secondCut < cols - 1; secondCut++) {
56            const leftArea: number = calculateRectangleArea(0, 0, rows - 1, firstCut);
57            const middleArea: number = calculateRectangleArea(0, firstCut + 1, rows - 1, secondCut);
58            const rightArea: number = calculateRectangleArea(0, secondCut + 1, rows - 1, cols - 1);
59            minArea = Math.min(minArea, leftArea + middleArea + rightArea);
60        }
61    }
62
63    // Try mixed cuts: one horizontal and one vertical cut in different configurations
64    for (let horizontalCut = 0; horizontalCut < rows - 1; horizontalCut++) {
65        for (let verticalCut = 0; verticalCut < cols - 1; verticalCut++) {
66            // Configuration 1: Top-left, top-right, bottom
67            const topLeft: number = calculateRectangleArea(0, 0, horizontalCut, verticalCut);
68            const topRight: number = calculateRectangleArea(0, verticalCut + 1, horizontalCut, cols - 1);
69            const bottom: number = calculateRectangleArea(horizontalCut + 1, 0, rows - 1, cols - 1);
70            minArea = Math.min(minArea, topLeft + topRight + bottom);
71          
72            // Configuration 2: Top, bottom-left, bottom-right
73            const top: number = calculateRectangleArea(0, 0, horizontalCut, cols - 1);
74            const bottomLeft: number = calculateRectangleArea(horizontalCut + 1, 0, rows - 1, verticalCut);
75            const bottomRight: number = calculateRectangleArea(horizontalCut + 1, verticalCut + 1, rows - 1, cols - 1);
76            minArea = Math.min(minArea, top + bottomLeft + bottomRight);
77          
78            // Configuration 3: Top-left, bottom-left, right
79            const topLeftAlt: number = calculateRectangleArea(0, 0, horizontalCut, verticalCut);
80            const bottomLeftAlt: number = calculateRectangleArea(horizontalCut + 1, 0, rows - 1, verticalCut);
81            const right: number = calculateRectangleArea(0, verticalCut + 1, rows - 1, cols - 1);
82            minArea = Math.min(minArea, topLeftAlt + bottomLeftAlt + right);
83          
84            // Configuration 4: Left, top-right, bottom-right
85            const left: number = calculateRectangleArea(0, 0, rows - 1, verticalCut);
86            const topRightAlt: number = calculateRectangleArea(0, verticalCut + 1, horizontalCut, cols - 1);
87            const bottomRightAlt: number = calculateRectangleArea(horizontalCut + 1, verticalCut + 1, rows - 1, cols - 1);
88            minArea = Math.min(minArea, left + topRightAlt + bottomRightAlt);
89        }
90    }
91
92    return minArea;
93}
94

Time and Space Complexity

Time Complexity: O(m^2 × n^2)

The analysis breaks down as follows:

  • The helper function f(i1, j1, i2, j2) iterates through a rectangular region, which takes O(m × n) time in the worst case.
  • The code has three main sections that enumerate different ways to partition the grid:
    1. Two horizontal cuts: O(m^2) iterations, each calling f three times
    2. Two vertical cuts: O(n^2) iterations, each calling f three times
    3. One horizontal and one vertical cut: O(m × n) iterations, each calling f three times (with 4 different partition patterns)
  • Since each call to f takes O(m × n) time, and we have:
    • O(m^2) iterations × O(m × n) = O(m^3 × n)
    • O(n^2) iterations × O(m × n) = O(m × n^3)
    • O(m × n) iterations × O(m × n) = O(m^2 × n^2)
  • The dominant term is O(m^2 × n^2), which determines the overall time complexity.

Space Complexity: O(1)

The space complexity is constant because:

  • The function f only uses a fixed number of variables (x1, y1, x2, y2)
  • The main function uses a fixed number of variables (m, n, ans, loop indices)
  • No additional data structures are created that scale with input size
  • The recursion depth is 1 (no recursive calls)

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

Common Pitfalls

1. Handling Empty Rectangles

The most critical pitfall in this solution is not handling cases where a partition region contains no 1s. When calculate_rectangle_area doesn't find any 1s in a subgrid, the min/max bounds remain at their initial infinity values, resulting in an invalid area calculation.

Problem Example:

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

If we partition this with a horizontal line after row 0 and another after row 1, the middle strip [1, 0, 2] contains no 1s, causing the function to return a negative or extremely large area.

Solution:

def calculate_rectangle_area(row1: int, col1: int, row2: int, col2: int) -> int:
    min_row = float('inf')
    min_col = float('inf')
    max_row = -float('inf')
    max_col = -float('inf')
  
    has_ones = False  # Track if we found any 1s
  
    for row in range(row1, row2 + 1):
        for col in range(col1, col2 + 1):
            if grid[row][col] == 1:
                has_ones = True
                min_row = min(min_row, row)
                min_col = min(min_col, col)
                max_row = max(max_row, row)
                max_col = max(max_col, col)
  
    # Return 0 if no 1s found, as empty rectangles are invalid
    if not has_ones:
        return float('inf')  # Return infinity to exclude this partition
  
    return (max_row - min_row + 1) * (max_col - min_col + 1)

2. Off-by-One Errors in Loop Boundaries

Another common mistake is incorrectly setting loop boundaries when iterating through possible partition positions.

Problem:

# Incorrect: doesn't leave space for third rectangle
for row1 in range(rows):  # Should be rows - 1
    for row2 in range(row1 + 1, rows):  # Should be rows - 1

Solution: Ensure each partition leaves at least one row/column for each rectangle:

# Correct: ensures all three rectangles have at least one row
for row1 in range(rows - 2):  # First cut can be at most at rows - 3
    for row2 in range(row1 + 1, rows - 1):  # Second cut leaves room for third rectangle

3. Incorrect Partition Configuration Logic

It's easy to mix up the coordinates when implementing the 6 different partition patterns, especially for L-shaped configurations.

Problem: Accidentally overlapping rectangles or missing parts of the grid:

# Incorrect: rectangles might overlap or miss cells
total_area = (
    calculate_rectangle_area(0, 0, row, col) +
    calculate_rectangle_area(0, col, row, cols - 1) +  # Should be col + 1
    calculate_rectangle_area(row, 0, rows - 1, cols - 1)  # Should be row + 1
)

Solution: Carefully verify that:

  • Adjacent rectangles share boundaries but don't overlap (use col + 1 and row + 1 for the next region)
  • All cells in the grid are covered exactly once
  • Draw out each configuration to visualize the partitions

4. Not Validating Input Constraints

The problem requires exactly 3 rectangles to cover all 1s. If the grid has fewer than 3 cells with 1s, the problem becomes impossible.

Solution: Add validation at the beginning:

def minimumSum(self, grid: List[List[int]]) -> int:
    # Count total number of 1s
    ones_count = sum(sum(row) for row in grid)
    if ones_count < 3:
        return -1  # Or handle according to problem requirements
  
    # Rest of the solution...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More