Problem Description

You are given a 2D binary array grid containing only 0s and 1s. Your task is to find the smallest rectangular region that can contain all the 1s in the grid.

The rectangle must have its sides parallel to the horizontal and vertical axes of the grid. You need to determine the minimum possible area of such a rectangle that encloses all 1s.

For example, if you have scattered 1s across the grid, you need to find the tightest bounding box that includes every single 1, then calculate and return its area.

The solution approach tracks the minimum and maximum row and column indices where 1s appear. By iterating through the entire grid and updating these boundaries whenever a 1 is found, we can determine:

• x1, y1: the minimum row and column indices containing a 1
• x2, y2: the maximum row and column indices containing a 1

The area of the minimum rectangle is then calculated as (x2 - x1 + 1) × (y2 - y1 + 1), where we add 1 to account for the inclusive nature of the boundaries.

Intuition

To find the smallest rectangle that contains all 1s, we need to think about what defines a rectangle's boundaries. A rectangle is uniquely determined by its top-left and bottom-right corners (or equivalently, its minimum and maximum coordinates).

Since we want the smallest possible rectangle that still contains all 1s, we need to find the tightest possible boundaries. This means:

• The topmost edge should be at the row of the topmost 1
• The bottommost edge should be at the row of the bottommost 1
• The leftmost edge should be at the column of the leftmost 1
• The rightmost edge should be at the column of the rightmost 1

If we push any boundary inward, we would exclude at least one 1 from the rectangle. If we push any boundary outward, we would unnecessarily increase the area.

Therefore, the key insight is that we only need to track four values while scanning through the grid:

• The minimum row index where we see a 1 (x1)
• The minimum column index where we see a 1 (y1)
• The maximum row index where we see a 1 (x2)
• The maximum column index where we see a 1 (y2)

Once we have these four boundaries, the rectangle is fully defined, and its area can be calculated as the product of its height (x2 - x1 + 1) and width (y2 - y1 + 1). The +1 is needed because both boundaries are inclusive - a rectangle from row 2 to row 4 has height 3, not 2.

Solution Approach

The implementation follows a straightforward scanning approach to find the minimum bounding rectangle:

1. Initialize boundary variables: We start by setting the minimum boundaries (x1, y1) to infinity and maximum boundaries (x2, y2) to negative infinity. This ensures that any valid coordinate we find will properly update these values.

2. Traverse the grid: We iterate through each cell in the grid using a nested loop:

   • The outer loop enumerate(grid) gives us each row with its index i
   • The inner loop enumerate(row) gives us each cell value with its column index j

3. Update boundaries when finding a 1: Whenever we encounter a cell with value 1, we update our four boundary variables:

   • x1 = min(x1, i): Update the minimum row index (top boundary)
   • y1 = min(y1, j): Update the minimum column index (left boundary)
   • x2 = max(x2, i): Update the maximum row index (bottom boundary)
   • y2 = max(y2, j): Update the maximum column index (right boundary)

4. Calculate the area: After scanning the entire grid, we have the tightest possible rectangle boundaries. The area is calculated as:

   • Height: (x2 - x1 + 1) - the number of rows from x1 to x2 inclusive
   • Width: (y2 - y1 + 1) - the number of columns from y1 to y2 inclusive
   • Area: (x2 - x1 + 1) * (y2 - y1 + 1)

This single-pass algorithm has a time complexity of O(m × n) where m and n are the dimensions of the grid, as we visit each cell exactly once. The space complexity is O(1) since we only use four variables to track the boundaries regardless of the input size.

Example Walkthrough

Let's walk through a small example to illustrate how the solution finds the minimum bounding rectangle.

Consider this 5×5 grid:

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

Step 1: Initialize boundaries

• x1 = ∞ (minimum row)
• y1 = ∞ (minimum column)
• x2 = -∞ (maximum row)
• y2 = -∞ (maximum column)

Step 2: Scan the grid row by row

Row 0: [0, 0, 0, 0, 0] - No 1s found, boundaries unchanged

Row 1: [0, 0, 1, 0, 0]

• Found 1 at position (1, 2)
• Update: x1 = min(∞, 1) = 1, y1 = min(∞, 2) = 2
• Update: x2 = max(-∞, 1) = 1, y2 = max(-∞, 2) = 2

Row 2: [0, 1, 0, 1, 0]

• Found 1 at position (2, 1)
  • Update: x1 = min(1, 2) = 1, y1 = min(2, 1) = 1
  • Update: x2 = max(1, 2) = 2, y2 = max(2, 1) = 2
• Found 1 at position (2, 3)
  • Update: x1 = min(1, 2) = 1, y1 = min(1, 3) = 1
  • Update: x2 = max(2, 2) = 2, y2 = max(2, 3) = 3

Row 3: [0, 0, 1, 0, 0]

• Found 1 at position (3, 2)
• Update: x1 = min(1, 3) = 1, y1 = min(1, 2) = 1
• Update: x2 = max(2, 3) = 3, y2 = max(3, 2) = 3

Row 4: [0, 0, 0, 0, 0] - No 1s found, boundaries unchanged

Step 3: Calculate the area

Final boundaries:

• Top boundary (x1) = 1
• Left boundary (y1) = 1
• Bottom boundary (x2) = 3
• Right boundary (y2) = 3

The minimum bounding rectangle spans:

• From row 1 to row 3 (inclusive)
• From column 1 to column 3 (inclusive)

This creates a 3×3 rectangle:

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

Area = (x2 - x1 + 1) × (y2 - y1 + 1) = (3 - 1 + 1) × (3 - 1 + 1) = 3 × 3 = 9

The algorithm successfully found the tightest rectangle that contains all four 1s in the grid, with an area of 9.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the grid. This is because the algorithm uses nested loops to iterate through every element in the 2D grid exactly once. The outer loop iterates through all m rows, and for each row, the inner loop iterates through all n columns, resulting in m × n total iterations. Each operation inside the loops (comparison and assignment) takes constant time O(1).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains four variables (x1, y1, x2, y2) to track the minimum and maximum coordinates, plus the loop variables i, j, and x. Since the number of variables remains constant and doesn't grow with the input size, the space complexity is constant.

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

Common Pitfalls

1. Empty Grid or No 1s Present

The current implementation doesn't handle the edge case where the grid is empty or contains no 1s at all. When no 1s are found, the boundary variables remain at their initial infinity values, leading to incorrect calculations or potential overflow errors.

Problem Example:

grid = [[0, 0, 0],
        [0, 0, 0]]  # No 1s present

This would result in height = float('-inf') - float('inf') + 1 which is undefined.

Solution: Add a check to handle this case:

def minimumArea(self, grid: List[List[int]]) -> int:
    min_row = float('inf')
    min_col = float('inf')
    max_row = float('-inf')
    max_col = float('-inf')
  
    found_one = False  # Track if we found any 1s
  
    for row_idx, row in enumerate(grid):
        for col_idx, cell_value in enumerate(row):
            if cell_value == 1:
                found_one = True
                min_row = min(min_row, row_idx)
                min_col = min(min_col, col_idx)
                max_row = max(max_row, row_idx)
                max_col = max(max_col, col_idx)
  
    # Return 0 if no 1s were found
    if not found_one:
        return 0
  
    height = max_row - min_row + 1
    width = max_col - min_col + 1
  
    return height * width

2. Incorrect Variable Naming Convention

Using generic names like x1, y1, x2, y2 can cause confusion about which dimension they represent. In many coordinate systems, x typically refers to the horizontal axis (columns) and y to the vertical axis (rows), but in 2D arrays, we often index by [row][column].

Solution: Use clear, descriptive variable names:

min_row, max_row  # Instead of x1, x2
min_col, max_col  # Instead of y1, y2

3. Off-by-One Error in Area Calculation

A common mistake is forgetting to add 1 when calculating the dimensions, which would exclude one boundary:

# Wrong:
area = (max_row - min_row) * (max_col - min_col)

# Correct:
area = (max_row - min_row + 1) * (max_col - min_col + 1)

The +1 is necessary because both boundaries are inclusive. For example, if min_row = 2 and max_row = 4, the rectangle spans rows 2, 3, and 4 (three rows total), not just two.