Find the Minimum Area to Cover All Ones I

medium array matrix bounding box

Problem

You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides that has the smallest area such that every 1 in grid lies inside it. Return that minimum area.

Because the rectangle is axis-aligned, the tightest box is bounded by the topmost, bottommost, leftmost, and rightmost 1. Its area is (maxRow − minRow + 1) × (maxCol − minCol + 1).

Inputgrid = [[0,1,0],[1,0,1]]

Output6

The ones span rows 0–1 and columns 0–2, so the box is 2 tall and 3 wide: 2 × 3 = 6.

grid (rows separated by ; cells by ,)

def minimumArea(grid):
    rows, cols = len(grid), len(grid[0])
    min_r, max_r = rows, -1          # row bounds of the 1's
    min_c, max_c = cols, -1          # column bounds of the 1's
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:      # a 1 — stretch the box to include it
                min_r = min(min_r, r)
                max_r = max(max_r, r)
                min_c = min(min_c, c)
                max_c = max(max_c, c)
    # area = height * width of the bounding box
    return (max_r - min_r + 1) * (max_c - min_c + 1)

function minimumArea(grid) {
  const rows = grid.length, cols = grid[0].length;
  let minR = rows, maxR = -1;          // row bounds of the 1's
  let minC = cols, maxC = -1;          // column bounds of the 1's
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) {          // a 1 — stretch the box to include it
        minR = Math.min(minR, r);
        maxR = Math.max(maxR, r);
        minC = Math.min(minC, c);
        maxC = Math.max(maxC, c);
      }
    }
  }
  // area = height * width of the bounding box
  return (maxR - minR + 1) * (maxC - minC + 1);
}

int minimumArea(int[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int minR = rows, maxR = -1;          // row bounds of the 1's
    int minC = cols, maxC = -1;          // column bounds of the 1's
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {       // a 1 — stretch the box to include it
                minR = Math.min(minR, r);
                maxR = Math.max(maxR, r);
                minC = Math.min(minC, c);
                maxC = Math.max(maxC, c);
            }
        }
    }
    // area = height * width of the bounding box
    return (maxR - minR + 1) * (maxC - minC + 1);
}

int minimumArea(vector<vector<int>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    int minR = rows, maxR = -1;          // row bounds of the 1's
    int minC = cols, maxC = -1;          // column bounds of the 1's
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 1) {       // a 1 — stretch the box to include it
                minR = min(minR, r);
                maxR = max(maxR, r);
                minC = min(minC, c);
                maxC = max(maxC, c);
            }
        }
    }
    // area = height * width of the bounding box
    return (maxR - minR + 1) * (maxC - minC + 1);
}

Explanation

The rectangle must have horizontal and vertical sides, so it is fully described by four numbers: the smallest and largest row that contains a 1, and the smallest and largest column that contains a 1. Any rectangle that covers all the ones must reach at least these four extremes, and the rectangle that reaches exactly these extremes is the smallest one possible.

So we never have to try different rectangles. We just scan the whole grid once, and whenever we meet a cell equal to 1 we update four running bounds: minR, maxR, minC, maxC. They start "inverted" (minR = rows, maxR = -1, etc.) so the very first 1 snaps them to real values.

After the scan, the bounding box spans rows minR…maxR and columns minC…maxC. Its height is maxR − minR + 1 and its width is maxC − minC + 1 — the + 1 counts the cells inclusively. The answer is height × width.

The problem guarantees at least one 1 exists, so the bounds are always set before we compute the area, and no special empty-grid case is needed.

Example: in [[0,1,0],[1,0,1]] the ones sit at rows 0 and 1 (so minR=0, maxR=1) and columns 0, 1, and 2 (so minC=0, maxC=2). Area = (1−0+1) × (2−0+1) = 2 × 3 = 6.

Time: O(rows · cols) Space: O(1)