Min boards to cover roof holes
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `m x n` binary grid `roof` representing a roof surface:
- `roof[i][j] = 1` means the cell is intact.
- `roof[i][j] = 0` means the cell is a hole that must be covered.
You can patch holes using wooden boards of two types:
1. A **vertical board** of size `m x 1` that covers **an entire column** (all rows in that column).
2. A **horizontal board** of size `1 x n` that covers **an entire row** (all columns in that row).
A board covers every cell it spans (intact or hole). You may place any number of boards.
Task: Return the **minimum number of boards** needed so that **every hole cell (`0`) is covered by at least one placed board**.
**Example**
```
roof = [
[1,0,1],
[0,1,1]
]
```
Holes are at `(0,1)` and `(1,0)`. One optimal solution is: cover **row 1** and **column 2** (or other equivalents) with 2 boards.
**Constraints (reasonable interview scale)**
- `1 <= m, n <= 2000`
- Total cells `m*n` can be large; aim for better than `O((mn)^2)`.
**Note**: This is a minimum-coverage question; your answer should be an integer minimum.
Quick Answer: This question evaluates competency in combinatorial optimization and problem modeling for coverage constraints, testing algorithmic reasoning, complexity analysis, and efficient representation of grid-based data.
You are given an m x n binary grid `roof` representing a roof surface. `roof[i][j] = 1` means the cell is intact, and `roof[i][j] = 0` means the cell is a hole.
You can place any number of wooden boards of two types:
- A vertical board covers an entire column.
- A horizontal board covers an entire row.
A hole at position `(i, j)` is considered covered if you place either the board for row `i`, the board for column `j`, or both. Boards may overlap, and they may also cover intact cells.
Return the minimum number of boards needed so that every hole cell is covered.
Example:
`roof = [[1,0,1],[0,1,1]]`
The holes are at `(0,1)` and `(1,0)`. The minimum number of boards needed is `2`.
Constraints
- 1 <= m <= 2000
- 1 <= n <= 2000
- roof[i][j] is either 0 or 1
- The grid can be large, so an O((m*n)^2) solution is too slow
Examples
Input: [[1,0,1],[0,1,1]]
Expected Output: 2
Explanation: The two holes are in different rows and different columns, so one board is not enough. Two boards are sufficient.
Input: [[1,1],[1,1]]
Expected Output: 0
Explanation: There are no holes, so no boards are needed.
Input: [[0]]
Expected Output: 1
Explanation: A single cell that is a hole can be covered by either its row board or its column board.
Input: [[0,0,0],[1,1,1]]
Expected Output: 1
Explanation: All holes are in the first row, so one horizontal board covering that row is enough.
Input: [[0,0],[0,0]]
Expected Output: 2
Explanation: One board cannot cover all four holes. Two boards are enough, for example both rows or both columns.
Input: [[0,1,1],[1,0,1],[1,1,0]]
Expected Output: 3
Explanation: Each hole is on a different row and different column pair, so at least three boards are needed.
Hints
- Think of each row and each column as a selectable object. Every hole must be covered by selecting at least one of its row or column.
- Model rows and columns as the two sides of a bipartite graph, and each hole as an edge. Then the task becomes finding the smallest set of vertices that touches every edge.