LeetCode 3195 - Find the Minimum Area to Cover All Ones I

The problem asks us to find the smallest rectangle that covers all the 1's in a given 2D binary grid. The grid consists of rows and columns where each cell is either 0 or 1.

leetcodemediumarraymatrix

LeetCode Problem 3195

Difficulty: 🟡 Medium
Topics: Array, Matrix

Solution

Problem Understanding

The problem asks us to find the smallest rectangle that covers all the 1's in a given 2D binary grid. The grid consists of rows and columns where each cell is either 0 or 1. The rectangle must have sides aligned with the grid axes, meaning its edges run along the rows and columns. The goal is to compute the area of this rectangle, which is the product of its height (number of rows) and width (number of columns).

The constraints indicate that the grid can be up to 1000x1000, which means a brute-force search through all possible rectangles could be very slow. The problem guarantees that there is at least one 1 in the grid, so we do not need to handle an empty grid. Edge cases to consider include a grid where all 1's are in the same row, the same column, or scattered irregularly, including cases where the grid has only one row or one column.

Approaches

Brute Force

The brute-force approach is to examine every possible rectangle in the grid, checking if it covers all the 1's. For each rectangle defined by a top-left corner (r1, c1) and bottom-right corner (r2, c2), we would iterate through all cells inside this rectangle to verify that all 1's are included. The area is then calculated and compared to maintain the minimum.

This approach is correct because it considers every possible rectangle, but it is far too slow. With a grid of size m x n, there are roughly (m*n)^2 rectangles, and checking each could take O(m_n), leading to a time complexity on the order of O((m_n)^3), which is impractical for m, n up to 1000.

Optimal Approach

The key observation is that to cover all 1's in a rectangle, we only need the minimum and maximum row indices and column indices that contain 1's. Let min_row and max_row be the smallest and largest row indices with a 1, and min_col and max_col be the smallest and largest column indices with a 1. The rectangle defined by these boundaries will cover all 1's and is guaranteed to have the smallest area.

Instead of searching all rectangles, we can scan the grid once to compute these four values. Then the area is simply (max_row - min_row + 1) * (max_col - min_col + 1). This reduces the time complexity from cubic to linear in the size of the grid.

Approach Time Complexity Space Complexity Notes
Brute Force O((m*n)^3) O(1) Checks all rectangles for coverage of 1's
Optimal O(m*n) O(1) Single pass to find min/max row/col of 1's

Algorithm Walkthrough

  1. Initialize four variables: min_row and min_col to infinity, max_row and max_col to -1. These will track the boundaries of 1's.
  2. Iterate through each cell (r, c) of the grid.
  3. If the current cell contains a 1, update the boundaries:
  • min_row = min(min_row, r)
  • max_row = max(max_row, r)
  • min_col = min(min_col, c)
  • max_col = max(max_col, c)
  1. After completing the iteration, calculate the rectangle's height as (max_row - min_row + 1) and width as (max_col - min_col + 1).
  2. Return the area as height * width.

Why it works: By maintaining the extreme row and column indices of 1's, we guarantee that all 1's are contained within the rectangle. Since any smaller rectangle would exclude a 1 at one of the extremes, this rectangle is minimal.

Python Solution

from typing import List

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        min_row, min_col = float('inf'), float('inf')
        max_row, max_col = -1, -1
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1:
                    min_row = min(min_row, r)
                    max_row = max(max_row, r)
                    min_col = min(min_col, c)
                    max_col = max(max_col, c)
        
        height = max_row - min_row + 1
        width = max_col - min_col + 1
        
        return height * width

The Python implementation initializes the boundaries and iterates through every cell to update them when a 1 is encountered. Once all boundaries are determined, it calculates the rectangle's dimensions and returns the area.

Go Solution

func minimumArea(grid [][]int) int {
    minRow, minCol := len(grid), len(grid[0])
    maxRow, maxCol := -1, -1
    
    for r := 0; r < len(grid); r++ {
        for c := 0; c < len(grid[0]); c++ {
            if grid[r][c] == 1 {
                if r < minRow {
                    minRow = r
                }
                if r > maxRow {
                    maxRow = r
                }
                if c < minCol {
                    minCol = c
                }
                if c > maxCol {
                    maxCol = c
                }
            }
        }
    }
    
    height := maxRow - minRow + 1
    width := maxCol - minCol + 1
    return height * width
}

In Go, we use slices for the grid and manage boundaries with integer variables. The logic mirrors the Python solution, with explicit if statements to update min/max values instead of using min/max functions.

Worked Examples

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

Step min_row max_row min_col max_col
Initial inf -1 inf -1
Cell (0,1)=1 0 0 1 1
Cell (1,0)=1 0 1 0 1
Cell (1,2)=1 0 1 0 2

Height = 2, Width = 3, Area = 6

Example 2: grid = [[1,0],[0,0]]

Step min_row max_row min_col max_col
Initial inf -1 inf -1
Cell (0,0)=1 0 0 0 0

Height = 1, Width = 1, Area = 1

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) We scan every cell of the grid once to find the min/max indices.
Space O(1) Only four variables are used regardless of grid size.

The algorithm is efficient because it avoids nested rectangle checks and only uses a single pass to determine the rectangle boundaries.

Test Cases

# Provided examples
assert Solution().minimumArea([[0,1,0],[1,0,1]]) == 6  # scattered 1's
assert Solution().minimumArea([[1,0],[0,0]]) == 1      # single 1

# Edge cases
assert Solution().minimumArea([[1]]) == 1              # smallest grid
assert Solution().minimumArea([[0,1,0,0],[0,1,0,0]]) == 2  # vertical rectangle
assert Solution().minimumArea([[1,1,1],[1,1,1]]) == 6     # full rectangle
assert Solution().minimumArea([[0,0,0,1]]) == 1          # 1 at the end of row
Test Why
[[0,1,0],[1,0,1]] Scattered 1's require rectangle expansion in both dimensions
[[1,0],[0,0]] Single 1 ensures minimal area of 1
[[1]] Minimal grid size
[[0,1,0,0],[0,1,0,0]] Vertical strip rectangle
[[1,1,1],[1,1,1]] Full rectangle coverage
[[0,0,0,1]] Edge column 1

Edge Cases

1. Single row or column with 1's: If the grid is a single row or column, the rectangle should correctly compute width or height as 1. The implementation handles this by calculating max - min + 1.

2. All 1's in one contiguous block: If all 1's form a complete rectangle, the algorithm still correctly identifies the bounding rectangle as that block.

3. Sparse 1's at corners: 1's only at corners of the grid could lead naive algorithms to miscalculate. Our solution tracks min/max indices independently, ensuring the rectangle spans all 1's correctly.